面試題 100 —— 5 查找 Top K
這里的做法是利用一個堆，用這個堆作為 K 個元素的輸出容器，堆的特點是可以以 O(1) 的效率去堆中最大/小的元素。
正式利用了這一點，這種方法的時間復雜度為 O(NlogK)
查找最小的 K 個數
利用最大堆
思路時，開始的時候堆為空，堆中元素個數還不足 K 個，所以遍歷的當前元素直接加入到堆中
當堆中元素等于 K 的時候，檢查當前元素與堆中最大元素的大小關系，若大于最大元素則忽略，否則將堆中最大元素刪除，并將當前元素添加到堆中。
整個過程，遍歷一遍集合，每次針對當前元素需要對堆進行調整，總的時間復雜度為 O(NlogK)
http://www.shnenglu.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 閱讀(303)
評論(0) 編輯 收藏 引用