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