堆

• 题意解析：找第k大元素——找前K大元素中的最小元素，因此维护一个大小为k的小根堆
• 所有元素Push进堆，最后堆中留下的便是前k大元素，堆顶为第K大元素
• 时间O(nlogk) 空间O(k)

class Solution {
public:

    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size()<k) return 0;
        priority_queue<int,vector<int>,greater<int>> heap;          //小顶堆

        for(const auto &c:nums)
        {
            heap.push(c);
            if(heap.size()>k) heap.pop();
        }
        return heap.top();
    }
};

快排partition思想

• 第1大的元素下标为n-1，第2大的元素下标为n-2，…,第k大元素在数组中的下标为n-k
• 快排partition函数每次将本轮pivot元素放到其排序后的位置，并返回该位置索引
• 若返回值大于n-k，表明第K大元素在pivot元素左边，则在左半边区间寻找第k大元素。
• 若返回值小于n-k，表明第K大元素在pivot元素右边，在右半边区间寻找。
• 若返回值等于n-k，表明找到第k大元素的位置，返回该位置元素即可。
• 时间复杂度:$O(n)$
• partition函数单次复杂度为线性复杂度，但每次调用时，区间会减少一部分，平均下来每次调用区间长度减半，因此 n+n/2+n/4…=O(n)

class Solution {
    //O(n)
    int partition(vector<int> &nums,int lo,int hi)
    {
        swap(nums[lo],nums[(lo+hi)>>1]);
        int pivot=nums[lo];

        while(lo<hi)
        {
            while(lo<hi && nums[hi]>pivot) hi--;
            if(lo<hi) nums[lo++]=nums[hi];
            while(lo<hi && nums[lo]<pivot) lo++;
            if(lo<hi) nums[hi--]=nums[lo]; 
        }
        nums[lo]=pivot;
        return lo;
    }
public:
    int findKthLargest(vector<int>& nums, int k){
        int n=nums.size();
        int target=n-k;         //第K大元素在数组中下标为n-k
        int lo=0,hi=n-1; 
        while (true) {
            int idx = partition(nums,lo,hi);
            if(idx<target) lo=idx+1;
            else if(idx>target) hi=idx-1;
            else return nums[idx];
        }
    }
};