给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 10(5)

-10(4) <= nums[i] <= 10(4)

首先想到使用小顶堆维护k个元素，处理完整个数组后堆顶即为所求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findKthLargest(vector<int> &nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 0; i < k; i++) {
            pq.push(nums[i]);
        }
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > pq.top()) {
                pq.push(nums[i]);
                pq.pop();
            }
        }
        return pq.top();
    }
};

还可以利用快速排序的划分，每次划分都能确定一个元素的位置，根据这个元素我们可以把数组分为两部分

这样再根据其中一部分的元素个数与k进行比较，我们能得到目标元素再哪部分再进行划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickSelect(nums, 0, n - 1, n - k);
    }
    int quickSelect(vector<int> &nums, int l, int r, int k) {
        if (l >= r)
            return nums[k];
        swap(nums[l], nums[l + rand() % (r - l + 1)]);

        int p = nums[l];
        int i = l;
        int j = r;
        while (i < j) {

            while (i < j && nums[j] >= p)
                j--;

            while (i < j && nums[i] <= p)
                i++;
            swap(nums[i], nums[j]);
        }
        swap(nums[i], nums[l]);
        if (i == k)
            return nums[i];
        if (i > k) {
            return quickSelect(nums, l, i - 1, k);
        }
        return quickSelect(nums, i + 1, r, k);
    }
};