Top K问题

参考网站

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

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return findK(nums, 0, nums.size() - 1, k);
    }
    
    int findK(vector<int>& nums, int l, int r, int k) {
        int re = partition(nums, l, r);
        if(re == nums.size() - k) return nums[re];
        else if(re < nums.size() - k) return findK(nums, re + 1, r, k);
        else return findK(nums, l, re - 1, k);
    }
    
    // 快速排序的分治思想
    int partition(vector<int>& nums, int l, int r) {
        int base = (rand() % (r - l + 1)) + l;
        swap(nums[l], nums[base]);
        int i = l+1, j = r;
        while(i <= j) {
            while(i <= r && nums[i] <= nums[l])
                ++i;
            while(j >= l && nums[j] >= nums[l])
                --j;
            if(i <= r && j >= l && i < j)
                swap(nums[i], nums[j]);
            else
                ++i;
        }
        if(j > l) {
            swap(nums[l], nums[j]);
            return j;
        }else return l;
        
    }
};