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

建堆，弹出k-1个后，顶部即为第K大

  1. class Solution {
  2. public:
  3.     void maxHeapDown(vector<int>& nums,int father,int heapSize){
  4.         int l=father*2+1;
  5.         int r=father*2+2;
  6.         int largest = father;
  7.         if(l<heapSize&&nums[l]>nums[largest]){
  8.             largest = l;
  9.         }
  10.         if(r<heapSize&&nums[r]>nums[largest]){
  11.             largest = r;
  12.         }
  13.         if(largest!=father){
  14.             swap(nums[father],nums[largest]);
  15.             maxHeapDown(nums,largest,heapSize);
  16.         }
  17.     }
  18.     void buildHeap(vector<int>& nums){
  19.         for(int i=nums.size()/2;i>=0;i--){
  20.             maxHeapDown(nums,i,nums.size());
  21.         }
  22.     }
  23.     int findKthLargest(vector<int>& nums, int k) {
  24.         buildHeap(nums);
  25.         int heapSize = nums.size();
  26.         for(int i=0;i<k-1;i++){
  27.             swap(nums[0],nums[heapSize-1]);
  28.             heapSize--;
  29.             maxHeapDown(nums,0,heapSize);
  30.         }
  31.         return nums[0];
  32.     }
  33. };