题解 | #寻找第K大#

class Solution { public: int findKth(vector a, int n, int K) { // write code here //不会快排的思路所以只能借助大根堆了，即出k次第k次的堆顶元素即为所求 for(int i=1;i<n;i++) { int ans=i; while(a[ans]>a[(ans-1)/2])//比我父亲要大就向上调成大根堆 { int temp=a[ans]; a[ans]=a[(ans-1)/2]; a[(ans-1)/2]=temp; ans=(ans-1)/2;//向上调整 } } //循环结束后数组就成了大根堆 //所以接下来只需要进行k次出堆顶元素即可 int target=-1; int heapSize=n; for(int i=1;i<=K;i++)//出k-1次 { target=a[0]; a[0]=a[--heapSize]; int ans=0; while(2ans+1<heapSize)//当存在左孩子就继续调整 { int max=(2ans+2>=heapSize||a[2ans+1]>a[2ans+2])?2ans+1:2ans+2;//将左右孩子较大的那一个的下标给max if(a[max]>a[ans]) { int temp=a[max]; a[max]=a[ans]; a[ans]=temp; ans=max;//ans向下调整 } else break; } } return target; } };