1.题目
2.思路
上个月学过这个思路——10G数中找到前5G大的数。
找到前k大，建立一个元素个数为k的小顶堆——这样小顶堆的堆顶在整个堆里就是“前K大”，而将数组剩下的元素依次和堆顶比较，如果大于则替换（相当于不断注入大元素到这个堆集合里，再通过优先队列priority_queue即堆自动堆重排序），最后的堆顶即整个数组的前k大。
3.代码
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int,vector<int>,greater<int> >minheap;//小顶堆 for(int i=0;i<k;i++){ minheap.push(nums[i]);//0到k-1 } for(int i=k;i<nums.size();i++){ if(nums[i]>minheap.top()){ minheap.pop(); minheap.push(nums[i]);//依次遍历，大就替换堆顶 } } return minheap.top(); } };
可以发现两个for循环可以结合起来：
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int,vector<int>,greater<int> >minheap;//小顶堆 for(int i=0;i<nums.size();i++){ minheap.push(nums[i]); if(nums[i]>minheap.top()){ minheap.pop(); //minheap.push(nums[i]);//依次遍历，大就替换堆顶 } } return minheap.top(); } };
