注意：如序列1，2，3，3，4，k = 3，答案是3不是2。

1.快速选择，时间复杂度：$O(n)$，空间复杂度：递归深度$O(log n)$，每层递归$O(1)$，相乘$O(log n)$，如果算上nums数组是$O(n)$

2.桶排序，时间复杂度$O(n)$，空间复杂度：$O(n)$，n是值域

3.权值线段树，时间复杂度$O((n + m )log n)$（n次插入m次询问），空间复杂度$O(n)$，n是值域

1.快速选择代码：

class Solution {
public:
    int quickSelect(vector<int>& nums, int l,int r, int k){
        if(l == r){
            return nums[k];
        }
        int partition = nums[l], i = l - 1, j = r + 1;
        while(i < j){
            do i++;while(nums[i] < partition);
            do j--;while(nums[j] > partition);
            if(i < j)swap(nums[i], nums[j]);
        }
        if(k <= j)return quickSelect(nums, l, j, k);
        else return quickSelect(nums, j + 1, r, k);
    }
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quickSelect(nums, 0, n - 1, n - k);
    }
};

2.桶排序代码：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int bucket[20010] = {0};
        int n = nums.size();
        for(int num : nums){
            bucket[num + 10000]++;
        }
        for (int i = 20000; i >= 0; i--) {
            k = k - bucket[i];
            if (k <= 0) {
                return i - 10000;
            }
        }
        return 0;
    }
};