直观的解法是对所有的 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 阅读(1130)
评论(3) 编辑 收藏 引用