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();
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

可以发现两个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();
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/113777304