Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array‘s length.
class Solution { public: void maxHeapify(vector<int>& a,int i,int heapSize){ int l = i*2+1,r = i*2 +2,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[i],a[largest]);//把当前节点和孩子节点中最大的节点进行交换 maxHeapify(a,largest,heapSize);//继续调整孩子节点之后的堆 } } void buildMaxHeap(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(); buildMaxHeap(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]; } };
注意：1.堆排序的写法，开始位置是0 2.注意每次建立完相应的堆后，都把堆中最大的数删除，然后重新调整堆，直到最后找到相应的数
Kth Largest Element in an Array
原文：https://www.cnblogs.com/zmachine/p/13673402.html