题解 | #最小的K个数#

class Solution { public: vector GetLeastNumbers_Solution(vector input, int k) { //思路：建一个小根堆，然后出k次堆顶元素即可，不知道能不能ac //首先把给的数组建成一个小根堆 //数组中i位置上的元素在堆上的父亲位置为（i-1）/2; for(int i=1;i<input.size();i++) { int ans=i; while(input[ans]<input[(ans-1)/2])//如果比他父亲还要小则向上调整 { int temp=input[ans]; input[ans]=input[(ans-1)/2]; input[(ans-1)/2]=temp; ans=(ans-1)/2;//向上调整 } } //循环结束后该数组就已经是个小根堆了 int heapSize=input.size();//heapSize决定小根堆的范围 vector array; for(int i=0;i<k&&heapSize>0;i++) { array.push_back(input[0]); input[0]=input[--heapSize]; int ans=0; while(2ans+1<heapSize)//即存在左孩子就循环 { int min=(input[2ans+1]>input[2ans+2]&&2ans+2<heapSize)?2ans+2:2ans+1; if(input[min]<input[ans]) { int temp=input[ans]; input[ans]=input[min]; input[min]=temp; ans=min;//向下调整 } else//如果左右孩子中的最小值都比根大则break； break; } } return array; } };