面试题 100 —— 5 查找 Top K
这里的做法是利用一个堆，用这个堆作为 K 个元素的输出容器，堆的特点是可以以 O(1) 的效率去堆中最大/小的元素。
正式利用了这一点，这种方法的时间复杂度为 O(NlogK)
查找最小的 K 个数
利用最大堆
思路时，开始的时候堆为空，堆中元素个数还不足 K 个，所以遍历的当前元素直接加入到堆中
当堆中元素等于 K 的时候，检查当前元素与堆中最大元素的大小关系，若大于最大元素则忽略，否则将堆中最大元素删除，并将当前元素添加到堆中。
整个过程，遍历一遍集合，每次针对当前元素需要对堆进行调整，总的时间复杂度为 O(NlogK)
http://www.cppblog.com/jake1036/archive/2011/05/16/146466.html
代码实现：
1 #include <iostream>
2 #include <vector>
3 #include <set>
4 using namespace std;
5
6 typedef vector<int> dataset;
7 typedef multiset<int, greater<int> > bigheap;
8
9 void findTopK(bigheap& bh, const dataset& ds, int k)
10 {
11 bh.clear();
12 for (dataset::const_iterator cit = ds.begin(); cit != ds.end(); ++cit)
13 {
14 if (bh.size() < k)
15 {
16 bh.insert(*cit);
17 }
18 else
19 {
20 bigheap::iterator it = bh.begin();
21 if (*it > *cit)
22 {
23 bh.erase(it);
24 bh.insert(*cit);
25 }
26 }
27 }
28 }
29
30 int main()
31 {
32 dataset ds;
33 for (int i = 100; i != 0; --i)
34 {
35 ds.push_back(i);
36 }
37 bigheap bh;
38 findTopK(bh, ds, 10);
39 for (bigheap::const_iterator cit = bh.begin(); cit != bh.end(); ++cit)
40 {
41 cout << *cit << endl;
42 }
43 return 0;
44 }
45
46
posted on 2011-07-12 17:46
unixfy 阅读(282)
评论(0) 编辑 收藏 引用