第K大数 小顶堆

寻找第K大

http://www.nowcoder.com/questionTerminal/e016ad9b7f0b45048c58a9f27ba618bf

小顶堆,堆顶为最小元素
空间复杂度O(K)

#include<queue>
class Finder {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        priority_queue<int, vector<int>, greater<int>> Q;
        for(auto x : a){
            Q.push(x);
            if(Q.size() > K){  //保证堆中不超过K个元素
                Q.pop();
            }
        }
        return Q.top();
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-01 21:31
投递虾皮信息等公司10个岗位 > 你都收到了哪些公司的感谢信?
点赞 评论 收藏
分享
勇敢的联想人前程似锦:如果我是你,身体素质好我会去参军,然后走士兵计划考研211只需要200多分。
点赞 评论 收藏
分享
OffersGettttt:为啥现在看到大多数公司都有提前实习的要求
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务