数组中的第K大元素：快速选择和大根堆小根堆，库大根堆

组中的第K大元素：快速选择和大根堆小根堆，库大根堆"/>

数组中的第K大元素：快速选择和大根堆小根堆，库大根堆

听说这玩意儿是面试重点。。。
比如快速选择：你不能说快排，说快排就寄，要用经过优化的快速选择算法：

class Solution {
public:int quickselect(vector<int>& nums, int l,int r,int ksmall){//if(l=r)return nums[l];int q=rand()%(r-l+1)+l;int key=nums[q];swap(nums[l],nums[q]);int i=l,j=r;while(i<j){while(i<j&&nums[j]>=key)j--;nums[i]=nums[j];while(i<j&&nums[i]<=key)i++;nums[j]=nums[i];}nums[i]=key;if(i==ksmall)return nums[i];else if(i>ksmall)return quickselect(nums,l,i-1,ksmall);return quickselect(nums,i+1,r,ksmall);//相当于不用排后面的值了，直接将时间复杂度优化到了n(o)。 }int findKthLargest(vector<int>& nums, int k) {return quickselect(nums,0,nums.size()-1,nums.size()-k);}
};

比如大根堆，你必须要自己手建一个出来

class Solution {
public:void maxheapify(vector<int>&a,int i,int heapsize){int l=i*2+1,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[i],a[largest]);maxheapify(a,largest,heapsize);//换了之后可能会影响子节点的堆关系所以要进去看。}}void buildheapify(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();buildheapify(nums,heapsize);for(int i=nums.size()-1;i>nums.size()-k;i--){swap(nums[0],nums[i]);//不断交换，容量减小相当于把最大值给弄出去了heapsize--;maxheapify(nums,0,heapsize);}return nums[0];}
};

小根堆：居然和大根堆实现有较大区别，不过本质差不多：

class Solution {public:int findKthLargest(vector<int>& nums, int k) {// 对前k个元素建成小根堆for (int i = 0; i < k; i++) {swim(nums, i);}// 剩下的元素与堆顶比较，若大于堆顶则去掉堆顶，再将其插入for (int i = k; i < nums.size(); i++) {if (nums[i] > nums[0]) {swap(nums[0], nums[i]);sink(nums, 0, k - 1);}}// 结束后第k个大的数就是小根堆的堆顶return nums[0];}private:// 上浮 从下到上调整堆void swim(vector<int>& heap, int i) {while (i > 0 && heap[i]<heap[(i - 1) / 2]) {swap(heap[i], heap[(i - 1) / 2]);i = (i - 1) / 2;}}// 下沉 从下到上调整堆void sink(vector<int>& heap, int i, int N) {while (2 * i + 1 <= N) {int j = 2 * i + 1;if (j + 1 <= N && heap[j + 1]< heap[j]) {j++;}if (heap[i]<heap[j]) {break;}swap(heap[i], heap[j]);i = j;}}
};

调库大根堆：

class Solution 
{
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, less<int>> maxHeap;for (int x : nums)maxHeap.push(x);for (int i = 0; i < k - 1; i ++)maxHeap.pop();return maxHeap.top();}
};