经常在网上看到有人讨论这个问题：
或者是其他类似的问题，今天我也简单地分析一下。
具体问题具体分析，既然这个题目只要求我们找出这m个数，没有要求对其进行排序，所以负担也就轻了，相应地也能采用更高效的数据结构和算法。如果不要求空间复杂度，并且m不大，我们可以开辟另外一个空间（S）存储这m个数，一般的时候空间复杂度要求都是较低的，所以我们也可以这样假设。n个数中的前m个数我们可以直接放在空间S中，当取第m + 1个数的时候，我们就要考虑这个数是否要加入到空间S中，如果加入，应该遵循一个什么样的替换规则。我们需要找出的是最小的m个数，所以这m个数中最大的数M就是基准，如果后续的数比M大，那么就不应该加入空间，如果比M小，就要加入空间。当新数N需要加入空间时，被挤掉的数肯定是先前最大的数M，那么新数应该放在哪个位置呢？复杂度集中在如何找出最大的数M和如何插入新数N。其实，这两个问题是相关的，焦点就积聚在搜索最大数据和插入新数据的操作上。也许大家已经想到了，最大堆不就正适合此种情况吗？其最大数就是根元素，查找的时间复杂度为O(1)，新数据的插入时间复杂度为O(log(n))，已经为理论上的最优解。
C++的程序源码：
|
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
vector<int> val, val2, val3;
vector<int>::iterator it;
int m = 3, n = 100, t;
srand(time(NULL));
for (int i = 0; i < n; i ++) {
t = random();
val2.push_back(t);
val3.push_back(t);
cout << t << " ";
}
cout << endl;
for (int i = 0; i < n; i ++) {
int t = val3[i];
if (val.size() < m) {
val.push_back(t);
push_heap(val.begin(), val.end());
continue;
}
if (t >= val[0])
continue;
pop_heap(val.begin(), val.end());
val[m - 1] = t;
push_heap(val.begin(), val.end());
}
cout << "Top " << m << ":" << endl;
for (int i = 0; i < m; i ++)
cout << val[i] << " ";
cout << endl;
sort_heap(val2.begin(), val2.end());
cout << "Sorted Top " << m << ":" << endl;
for (int i = 0; i < m; i ++)
cout << val2[i] << " ";
cout << endl;
return 0;
}
|
代码很简单，如果你足够细心你会发现这个算法的实际时间复杂度为:
为什么多了系数2呢？因为pop_heap和push_heap的时间复杂度都为log(m)，且每次空间S的更新操作都需要做这两步。再次考察这两个操作，如果你熟悉heap，就会发现pop_heap和push_heap两步可以合并成一步，请看pop_heap的主要步骤:
- 将根元素取下来。
- 将末尾的元素取下来。
- 从根开始搜索将第2步取下的元素插入到堆中的适当位置。
因为我们在pop之后马上就需要再次push，所以两步可以合并为：
- 将根元素去下来。
- 从根开始搜索将要push的元素插入到堆中的适当位置。
具体代码请看客自己实现吧，不要太懒了，懒惰可不是什么好毛病！
另外，C++的STL也有相关算法模板:
| template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp); |
用其改写的上述代码简单了很多:
| #include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
vector<int> val, val2;
int m = 3, n = 100, t;
srand(time(NULL));
for (int i = 0; i < n; i ++) {
t = random();
val.push_back(t);
val2.push_back(t);
cout << t << " ";
}
cout << endl;
nth_element(val.begin(), val.begin() + m - 1, val.end());
cout << "Top " << m << ":" << endl;
for (int i = 0; i < m; i ++)
cout << val[i] << " ";
cout << endl;
sort(val2.begin(), val2.end());
cout << "Sorted Top " << m << ":" << endl;
for (int i = 0; i < m; i ++)
cout << val2[i] << " ";
cout << endl;
return 0;
} |
以上代码也算是nth_element应用的一个范例吧，至于它的具体实现，如果感兴趣还是自己分析，目前我也没有详细看。
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 