从n个数中提取最小的m个数的算法

经常在网上看到有人讨论这个问题：

如何高效地从n个数中提取最小的m个数？

或者是其他类似的问题，今天我也简单地分析一下。

具体问题具体分析，既然这个题目只要求我们找出这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;
}


代码很简单，如果你足够细心你会发现这个算法的实际时间复杂度为:

n * 2 * log ( m )

为什么多了系数2呢？因为pop_heap和push_heap的时间复杂度都为log(m)，且每次空间S的更新操作都需要做这两步。再次考察这两个操作，如果你熟悉heap，就会发现pop_heap和push_heap两步可以合并成一步，请看pop_heap的主要步骤:

1. 将根元素取下来。
2. 将末尾的元素取下来。
3. 从根开始搜索将第2步取下的元素插入到堆中的适当位置。

因为我们在pop之后马上就需要再次push，所以两步可以合并为：

1. 将根元素去下来。
2. 从根开始搜索将要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应用的一个范例吧，至于它的具体实现，如果感兴趣还是自己分析，目前我也没有详细看。