用快速排序的思想解决 数组中第K个最大元素

用快速排序的思想解决 数组中第K个最大元素

思路：题目限定使用快排思想，就直接舍弃用最小堆这种办法。

第一种方法：直接进行一遍快排，然后取倒数第K个元素即可。

第二种方法：是优化后的快排，因为我们只需要找到倒数第K 个元素即可，因此没必要把全部元素都排一遍，所以在排序的时候如果发现当前快速排序所排序元素的下标等于n-K就终止排序即可！

class Solution {
public:
    int k;
    int findKthLargest(vector& nums, int k) {
        this->k = k;
        quickSort(nums, 0, nums.size()-1);
        return nums[nums.size()-k];
    }
    void quickSort(vector& nums, int left, int right){
        if(left >= right) return;
        int i=left, j=right;
        int x = rand() % (right-left+1)+left;
        swap(nums[x], nums[left]);
        int key = nums[left];
        while(i != j){
            while(i=key){
                j--;
            }
            while(i nums.size()-k){
            quickSort(nums, left, i-1);
        }
    }
};

第三种方法：优化后的堆排序，自己建大顶堆，然后把前K-1个最大值弹出，最后返回最顶部元素

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        buildHeap(nums, nums.size());
        for(int i=nums.size()-1; i>=nums.size()-k+1; --i){
            swap(nums[0], nums[i]);
            heapify(nums, 0, i-1);
        }
        return nums[0];
    }
    void heapify(vector& nums, int i, int n){
        if(i >= n) return;
        int c1 = 2*i+1;
        int c2 = 2*i+2;
        int max1 = i;
        if(c1& nums, int n){
        int lastNode = n-1;
        int parent = (lastNode-1)/2;
        for(int i=parent; i>=0; --i){
            heapify(nums, i, n);
        }
    }
};