C++面试题之最小的K个数(topK问题) 题解
c++面试题之最小的k个数(topk问题) 题解
题目:输入n个整数,找出其中最小的k个数。例如:例如输入4 、5 、1、6、2、7、3 、8 这8 个数字,则最小的4 个数字是1 、2、3 、4
分析:
想到3种方法,第1种是先快排,然后挑出其中的前k个,时间复杂度为o(n logn);第2种方法是使用partition函数(进行一次快速排序用哨兵数分割数组中的数据),时间复杂度:o(n);第3种是小顶堆(优先队列),时间复杂度:o(n logk). 第3种在海量计算中应用广泛...
stl中的优先队列默认是大顶堆,此题是生成一个小顶堆,即可解决...
堆排序
数据对象为:数组,链表,不稳定,时间复杂度为o(n logk),空间复杂度为o(1),(最大堆,有序区)从堆顶把根卸出来放在有序区之前,再恢复堆。
priority_queue调用 stl里面的 make_heap(), pop_heap(), push_heap() 算法实现,也算是堆的另外一种形式。
方法3 大顶二叉堆
ac代码:
#include<cstdio> #include<vector> #include<queue> // 用到其中的优先队列priority_queue using namespace std; class solution { public: vector<int> getleastnumbers_solution(vector<int> input, int k) { vector<int> res; if(k<=0 || k>input.size()) return res; priority_queue<int> q; // stl中的优先队列默认是大顶堆 unsigned int i=0; while(i<input.size()) { q.push(input[i]); if(q.size()>k) q.pop(); i++; } while(!q.empty()) { res.push_back(q.top()); // c语言中的top()可返回顶部元素的值,也可返回顶部元素的指针,程序员自行设计; c++的stl中top()返回的是顶部的值 q.pop(); } return res; } }; // 以下为测试部分 int main() { solution sol; vector<int> vec1={2,5,3,7,9,8,6}; vector<int> vec2={5,7,6,9,11,10,8}; vector<int> vec3={7,4,6,5}; vector<int> res1=sol.getleastnumbers_solution(vec1,3); vector<int> res2=sol.getleastnumbers_solution(vec2,5); vector<int> res3=sol.getleastnumbers_solution(vec3,2); for(int i:res1) printf("%d ", i); printf("\n"); for(int i:res2) printf("%d ", i); printf("\n"); for(int i:res3) printf("%d ", i); printf("\n"); return 0; }
priority_queue函数列表
函数 |
描述 |
构造析构 |
|
priority_queue |
创建一个空的queue 。 |
数据访问与增减 |
|
c.top() |
返回队列头部数据 |
c.push(elem) |
在队列尾部增加elem数据 |
c.pop() |
队列头部数据出队 |
其它操作 |
|
c.empty() |
判断队列是否为空 |
c.size() |
返回队列中数据的个数 |
可以看出priority_queue的函数列表与栈stack的函数列表是相同的。
方法2 partition函数
ac代码:
#include<cstdio> #include<vector> using namespace std; class solution{ public: int partion(vector<int> a,int len,int low,int high) { int base=a[low]; int i=low, j=high; while(i != j) { while(i<j && a[j]>=base) j--; while(i<j && a[i]<=base) i++; if(i<j) // 交换 { int temp=a[i]; a[i]=a[j]; a[j]=temp; } } a[low]=a[i]; a[i]=base; return i; } vector<int> getleastnumbers_solution(vector<int> input, int k) { vector<int> res; int len=input.size(); if(len<=0) return res; int start=0; int end=len-1; int index=partion(input,len,start,end); while(k-1 != index) { if(k-1 < index) { end=index-1; index=partion(input,len,start,end); } else { start=index+1; index=partion(input,len,start,end); } } for(int i=0;i<k;i++) res.push_back(input[i]); return res; } }; // 以下为测试部分 int main() { solution sol; vector<int> vec1={2,5,3,7,9,8,6}; vector<int> vec2={5,7,6,9,11,10,8}; vector<int> vec3={7,4,6,5}; vector<int> res1=sol.getleastnumbers_solution(vec1,3); vector<int> res2=sol.getleastnumbers_solution(vec2,5); vector<int> res3=sol.getleastnumbers_solution(vec3,2); for(int &i:res1) printf("%d ", i); printf("\n"); for(int &i:res2) printf("%d ", i); printf("\n"); for(int &i:res3) printf("%d ", i); printf("\n"); return 0; }
其实还有一种思路:
可以用较为hack的手段进行。比如要获得一个堆中的最小值:
priority_queue<int> pq; pq.push( -1 * v1) ; pq.push( -1 * v2) ; pq.push( -1 * v3) ;
分别是插入v1, v2, v3变量的相反数,那么取相反数后的这些值变相构成为了最大堆,只是每次从pq取值后,要再次乘以-1即可获得堆中最小值...
上一篇: HGDB如何查看当前会话的pid
下一篇: Java数据库DBUtils框架使用介绍