解决面试问题中的top k问题 Leetcode

佚名 6年前 (2019-05-10) 随笔 1021人围观抢沙发百度已收录

https://leetcode.com/problems/kth-largest-element-in-an-array/

使用堆

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);
          for (int num : nums) {
            if (minQueue.size() < k || num > minQueue.peek())
              minQueue.offer(num);
            if (minQueue.size() > k)
              minQueue.poll();
          }
          return minQueue.peek();
    }
}

C++的

class Solution
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        priority_queue<int, vector<int>, greater<int> >pq;
        for(auto num:nums)
        {

            if(pq.size()<k)
                pq.push(num);
            else if(num>pq.top())
                pq.pop(),pq.push(num);
        }
        return pq.top();
    }
};