面試題 100 —— 5 查找 Top K
這里的做法是利用一個(gè)堆，用這個(gè)堆作為 K 個(gè)元素的輸出容器，堆的特點(diǎn)是可以以 O(1) 的效率去堆中最大/小的元素。
正式利用了這一點(diǎn)，這種方法的時(shí)間復(fù)雜度為 O(NlogK)
查找最小的 K 個(gè)數(shù)
利用最大堆
思路時(shí)，開始的時(shí)候堆為空，堆中元素個(gè)數(shù)還不足 K 個(gè)，所以遍歷的當(dāng)前元素直接加入到堆中
當(dāng)堆中元素等于 K 的時(shí)候，檢查當(dāng)前元素與堆中最大元素的大小關(guān)系，若大于最大元素則忽略，否則將堆中最大元素刪除，并將當(dāng)前元素添加到堆中。
整個(gè)過程，遍歷一遍集合，每次針對(duì)當(dāng)前元素需要對(duì)堆進(jìn)行調(diào)整，總的時(shí)間復(fù)雜度為 O(NlogK)
http://www.shnenglu.com/jake1036/archive/2011/05/16/146466.html
代碼實(shí)現(xiàn)：
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 閱讀(301)
評(píng)論(0) 編輯 收藏 引用