Leetcode 215 - Kth Largest Element in an Array（二分）

题意

求一个未排序数组的第k大。

思路

算法1

O(nlogn)$O(nlogn)$的复杂度。

先排序，然后直接返回第k大即可。

算法2

期望时间为O(n)$O(n)$，最坏时间为O(n2)$O(n^2)$的算法。

其基本思想就是基于快排。

首先，我们选择一个观察哨x，将≥x$/geq x$的元素放在x左边，小于x的元素放在x的右边。

然后，如果x此时的位置pos+1==k$pos + 1 == k$，说明x即为我们要求的元素。

否则， 如果pos+1>k$pos + 1 > k$，说明x过小，那么要求的元素应该在[l, pos - 1]之间。

否则， 要求的元素在[pos + 1, r]之间。

在算导第三版的P120-P122有对该算法时间复杂度的证明。

代码