题目描述 数组中的第K个最大元素

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

示例

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

解题思路

维护一个最小堆

代码一

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int> > heap;//最小堆
        for(int i =0;i<nums.size();++i)
        {
            if(heap.size()<k)
                heap.push(nums[i]);
            else{
                if(nums[i]>heap.top())
                {
                    heap.pop();
                    heap.push(nums[i]);
                }
            }
        }
        return heap.top();
    }
};

代码二

class Solution {
public:
    void maxHeap(vector<int> &nums, int i, int high){
        int left = 2*i+1, right = 2*i+2;
        int largest;
        if(left<high&&nums[left]>nums[i]) largest = left;
        else largest = i;

        if(right<high&&nums[right]>nums[largest]) largest = right;

        if(largest!=i){
            swap(nums[i], nums[largest]);
            maxHeap(nums, largest, high);
        }
    }

    void bulidHeap(vector<int> &nums){
        for(int i=nums.size()/2-1; i>=0; i--){
            maxHeap(nums, i, nums.size());
        }
    }


    void heapSort(vector<int> &nums){
        bulidHeap(nums);
        for(int i=nums.size()-1; i>0; i--){
            swap(nums[0], nums[i]);
            maxHeap(nums, 0, i);
        }
    }

    int findKthLargest(vector<int>& input, int k) {
        vector<int> nums(input.begin(), input.begin()+k);

        heapSort(nums);
        for(auto num:nums) cout << num << " ";
        cout << endl;
        for(int i=k;i<input.size();i++){
            if(input[i]>nums[0]){
                nums[0] = input[i];
                heapSort(nums);
            }
        }
        return nums[0];
    }
};