之前面试的时候，被问到，我的回答是每次都取头部进行比较，然后再取剩下的进行比较。身为菜鸡的我思路有了，却写不出来，后面想一想，这种topk问题，不就是堆问题解决吗？唉。菜鸡的悲哀。
如果已知多个个数列， 求n小==》 建立大根堆 。求n大==》 建立小根堆。原因主要是为了取堆顶元素比较大小。求n小代码如下 先来看看一个无序数组求topk 用优先队列
using namespace std; #include<iostream> #include<queue> #include<vector> //求一组数中最小的n个数 using namespace std; class Solution { public: //获取数组中第n个小的数 vector <int> Get_min_k(vector<int> v, int k) { //对于sort()函数，传入的第三个参数如果是less<int>()，则为大顶堆 //对于priority_queue，传入的第三个参数如果是greater<int>，为小顶堆 priority_queue<int, vector<int>, less<int> > q; //less<int> 代表大顶堆 vector <int> ret; for(int i=0;i<v.size() &&i< k;i++) { q.push(v[i]); } for (int i = k;i < v.size();i++) { if (v[i] < q.top())//小的话放进去 { q.pop(); q.push(v[i]); } } int i = 1; while (!q.empty()) { ret.emplace_back(q.top()); q.pop(); i++; } return ret; } }; int main() { vector<int> v{ 5,3,6,8,1,2,3,56,23,65,3,6 }; //vector<int> v{ 5,3,2,1,11,3,6 }; Solution s; vector<int> ret = s.Get_min_k(v, 5); int i = 1; //倒序输出即可 for (auto it = ret.rbegin(); it != ret.rend(); it++, i++) { cout << "第" << i << "个元素为" << *it << endl; } cout << "asdas"; }2020.10.5
