LeetCode HOT100 - 数组中的第K个最大元素

主要是时间复杂度有所限制

如果单纯从第 k 大角度出发的话，排序，红黑树，或者是用两个堆都可以去解决

但 O(n) 的话使用的是快速查找，解决的是找某个最终下标上的元素的问题

从区间的角度来说，快速查找的思路类似于二分，每次操作完后变化操作的区间

每次选择一个 pivot ，把大于 pivot 的放在 pivot 左侧，否则放在右侧

这样处理完成后

• p 左边一定都不大于它
• p 右边一定都不小于它

这时分三种情况：

1. 情况 1：p == target
   说明 pivot 正好就是我们要找的数，直接返回。

2. 情况 2：p < target
   说明答案在右边。
   因为左边加上 pivot 这些元素的排名都太靠前了，不可能是 target。
   所以只要在区间 [p+1, r] 继续找。

3. 情况 3：p > target
   说明答案在左边。
   所以只要在区间 [l, p-1] 继续找。

核心在于借用快排的一次 partition，但每次只去真正可能包含答案的那一边继续找，但快排左右两边都要排，快速选择只进一边，因为我们只需要第 k 大，不需要整个数组有序

使用随机数是为了避免一些最坏的情况，比如数组本来有序之类

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int p = partition(nums, l, r);
            if (p == k - 1) {
                return nums[p];
            } else if (p < k - 1) {
                l = p + 1;
            } else {
                r = p - 1;
            }
        }
        return -1;
    }

    int partition(vector<int>& nums, int l, int r) {
        int idx = l + rand() % (r - l + 1);
        swap(nums[idx], nums[r]);

        int pivot = nums[r];
        int i = l;

        for (int j = l; j < r; j++) {
            if (nums[j] > pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[r]);
        return i;
    }
};