直觀的解法是對所有的 N 個數進行排序，再取最前或最后的 k 個元素。
這種做法的時間復雜度為 O(NlogN) 。
一種較好的解法是：維持一個 k 個元素的集合 S，遍歷 N 個數，對每個元素，首先檢查 S 中的元素個數是否小于 k，如果小于直接加入到 S 中。如果 S 中已有 k 個元素，則比較待處理元素與 S 中最大的元素的大小關系，若小于 S 中最大的元素，則刪除 S 中最大的元素，并將該元素加入到 S 中。
怎樣才能快速地從 S 中尋找到我們想要的最大的元素，使用堆是個好方法，最大堆。每次直接去堆的第一個元素即是 S 中最大的元素。如果將 S 中的最大元素刪除，然后將 最后的一個元素放在堆頂，下滑，已調整堆。在講新的元素加入到堆中，上滑，以調整堆。可以將這兩個過程合并，即將 S 中最大的元素替換為 待處理的元素。對這個堆頂上的元素下滑，以調整堆。這里的復雜度為 O(Nlogk)。
STL 中的 multimap 不是堆，但是其可以以 O(logn) 維護其有序性，所以可以直接用 multimap 代替堆來實現。
http://zhedahht.blog.163.com/blog/static/2541117420072432136859/
1 #include <iostream>
2 #include <vector>
3 #include <set>
4 #include <ctime>
5 using namespace std;
6
7 void findMinK(multiset<int, greater<int> >& Kdata, int k, const vector<int>& data)
8 {
9 Kdata.clear();
10 int m = 0;
11 for (vector<int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
12 {
13 if (m < k)
14 {
15 Kdata.insert(*cit);
16 ++m;
17 }
18 else
19 {
20 if (*cit < *(Kdata.begin()))
21 {
22 Kdata.erase(Kdata.begin());
23 Kdata.insert(*cit);
24 }
25 }
26 }
27 }
28
29 int main()
30 {
31 vector<int> data;
32 srand(time(0));
33 int n = 100;
34 while (n--)
35 {
36 data.push_back(rand());
37 }
38 multiset<int, greater<int> > Kdata;
39 findMinK(Kdata, 10, data);
40 for (vector<int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
41 {
42 cout << *cit << ' ';
43 }
44 cout << endl;
45 for (multiset<int, greater<int> >::const_iterator cit = Kdata.begin(); cit != Kdata.end(); ++cit)
46 {
47 cout << *cit << ' ';
48 }
49 cout << endl;
50 return 0;
51 }
posted on 2011-04-26 22:59
unixfy 閱讀(1170)
評論(3) 編輯 收藏 引用