215.数组中的第 K 个最大元素 (Medium)*

class Solution {
public:
    // 日常复习快排
    void quickSort(vector<int>& nums, int l, int r) {
        int pos = 0;
        if(l < r) {
            int pivot = nums[l];
            int i = l, j = r;
            while(i < j) {
                while(i < j && nums[j] >= pivot) {
                    j--;
                }
                if(i < j) {
                    nums[i] = nums[j];
                    i++;
                }
                while(i < j && nums[i] <= pivot) {
                    i++;
                }
                if(i < j) {
                    nums[j] = nums[i];
                    j--;
                }
                nums[i] = pivot;
            }
            quickSort(nums, l, i - 1);
            quickSort(nums, i + 1, r);
        }
    }   
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums, 0, nums.size() - 1);
        return nums[nums.size() - k];
    }
};

class Solution {
public:
    // 快排 8 太适合这个问题，用堆排
    int heapSort(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> res;
        for(int i = 0; i < nums.size(); i++) {
            res.push(nums[i]);
            if(res.size() > k) {
                res.pop();
            }
        }
        return res.top();
    }
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums, 0, nums.size() - 1);
        return nums[nums.size() - k];
    }
};

class Solution {
private:
    int target;
    int n;
public:
    int findKthLargest(vector<int>& nums, int k) {
        n = nums.size();
        target = n - k;
        quickSort(nums, 0, n - 1);
        return nums[target];
    }
    void quickSort(vector<int>& nums, int l, int r) {
        if(l > r) {
            return;
        }
        swap(nums[l], nums[l + rand() % (r - l + 1)]);
        int finalPos = l + 1;
        for(int i = l + 1; i <= r; i++) {
            if(nums[i] < nums[l]) {
                swap(nums[i], nums[finalPos++]);
            }
        }
        swap(nums[l], nums[--finalPos]);
        if(finalPos == target) {
            return;
        }else if(finalPos > target) {
            quickSort(nums, l, finalPos - 1);
        }else {
            quickSort(nums, finalPos + 1, r);
        }
    }
};