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

思路

快速选择

代码

class Solution {
   
public:
    int partition(vector<int> &nums, int l, int r) {
   
        int p = rand() % (r - l + 1) + l;
        swap(nums[p], nums[r]);
        int store_index = l;
        for (int i = l; i <= r; i++) {
   
            if (nums[i] < nums[r]) {
   
                swap(nums[i],nums[store_index]);
                store_index++;
            }
        }
        swap(nums[store_index], nums[r]);
        return store_index;
    }
    int _findKthLargest(vector<int>& nums, int l, int r, int k) {
   
        if (l == r) return nums[l]; 
        int p = partition(nums, l, r);
        if (p - l + 1 == k) return nums[p];
        if (p - l + 1 > k) return _findKthLargest(nums, l, p - 1, k);
        else return _findKthLargest(nums, p + 1, r, k - p + l - 1);
    } 
    int findKthLargest(vector<int>& nums, int k) {
   
        return _findKthLargest(nums, 0, nums.size() - 1, nums.size() - k + 1); 
    }
};
执行用时 : 12 ms, 在所有 C++ 提交中击败了 93.95% 的用户

总结

  1. p - l + 1 与 k 等价
  2. 注意partation 的实现，如果不是随机的会很慢。