215. 数组中的第K个最大元素

#

题目

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

思路

1. 建立最大堆
2. 交换堆尾元素与堆顶元素，此时堆尾是最大值，然后heapsize-1，相当于删除最大值，然后重新调整为最大堆
3. 重复k-1次步骤2 ，堆顶元素nums[0]即为第k大的数

代码

class Solution {
public:
    void maxHeapify(vector<int>& a,int i,int heapsize){
        int l = i*2+1;
        int r = i*2+2;
        int largest = i;
        if(l<heapsize && a[l]>a[largest]){
            largest = l;
        }
        if(r<heapsize && a[r]>a[largest]){
            largest = r;
        }
        if(largest!=i){
            swap(a[largest],a[i]);
            maxHeapify(a,largest,heapsize);
        }
    }
    void build(vector<int>& a,int heapsize){
        for(int i = heapsize/2;i>=0;--i){
            maxHeapify(a,i,heapsize);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        int heapsize = nums.size();
        build(nums,heapsize);
        for(int i = nums.size()-1;i>=nums.size()-k+1;--i){
            swap(nums[0],nums[i]);
            heapsize--;
            maxHeapify(nums,0,heapsize);
        }
        return nums[0];
    }
};