寻找最小的 k 个数

题目描述：

输入 n 个整数，输出其中最小的 k 个。

分析和解法：

解法一：排序输出

要求一个序列中最小的 k 个数，按照惯有的思维方式，则是先对这个序列从小到大排序，然后输出前面的最小的 k 个数。
当然，选取什么排序算法都是可以的。为了效率，我们可以使用快排来进行排序，然后再遍历序列中前k个元素输出即可。
源代码如下：

#include <iostream>
#include <cstdlib>

using namespace std;

int Compare(const void *elem1, const void *elem2)
{
    return *((int *)(elem1)) - *((int *)(elem2));
}

int main()
{
    int a[100];
    int i = 0;
    char ch;
    while((ch = cin.get()) != '\n')  //此处也可以用 cin.peek() ，只预读，不取出 
    {
        cin.unget();
        cin >> a[i++];
    }
    int k;
    cin >> k;
    qsort(a, i, sizeof(int), Compare);
    if (i >= k)
    {
        for (int j = 0; j < k; j++)
            cout << a[j] << " ";
        cout << endl;
    }
    else 
        cout << "error: i < k";
    return 0;
}

分析：时间复杂度为 O（n * log n），但是这个方法修改了原有数据顺序，如果要求不许改变原始数据，则可以复制到另一数组去做。虽然可以解决问题，但是却做了许多无用功。

解法二：部分排序

题目没有要求最小的 k 个数有序，也没要求最后 n - k 个数有序。既然如此，就没有必要对所有元素进行排序。这时，就可以用选择排序或交换排序，即：

• 1、遍历 n 个数，把最先遍历到的 k 个数存入到大小为 k 的数组中，假设它们即是最小的 k 个数；
• 2、对这 k 个数，利用选择或交换排序找到这 k 个元素中的最大值kmax（找最大值需要遍历这 k 个数，时间复杂度为 O（k））；
• 3、继续遍历剩余 n - k 个数。假设每一次遍历到的新的元素的值为 x ，把 x 与 kmax 比较：如果 x < kmax ，用 x 替换 kmax，并回到第二步重新找出 k 个元素的数组中最大元素 kmax；如果 x >= kmax ，则继续遍历不更新数组。

源代码如下：

#include <iostream>
#include <cstdlib>

using namespace std;

void Swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp; 
}

int FindKMAX(int a[], int k)
{
    for(int i = 1; i < k; i++)
        if (a[0] < a[i])  Swap(a[0], a[i]);
    return a[0];  // a[0] 是 KMAX 
}

int main()
{
    int a[100];
    int i = 0;
    char ch;
    while((ch = cin.get()) != '\n')  //此处也可以用 cin.peek() ，只预读，不取出 
    {
        cin.unget();
        cin >> a[i++];
    }
    int k;
    cin >> k;
    int KMAX = FindKMAX(a, k);
    for (int j = k; j < i; j++)
    {
        if (KMAX > a[j])
            Swap(a[0], a[j]);
        else 
            continue;
        KMAX = FindKMAX(a, k);
    }
    for (int j = 0; j < k; j++)
        cout << a[j] << " ";
    cout << endl;
    return 0;
}

分析：每次遍历，更新或不更新数组的所用的时间为 O（k） 或 O（0） 。故整趟下来，时间复杂度为 n * O（k）=O（n * k） 。这种方法是无序输出的，只关心最小的 k 个数，具体谁大谁小并不关心。

解法三：维护最大堆

更好的办法是维护容量为k的最大堆，原理跟解法二的方法相似：

• 1、用容量为 k 的最大堆存储最先遍历到的 k 个数，同样假设它们即是最小的 k 个数；
• 2、堆中元素是有序的，令 k1 < k2 < ... < kmax （kmax 设为最大堆中的最大元素）
• 3、遍历剩余 n - k 个数。假设每一次遍历到的新的元素的值为 x，把 x 与堆顶元素 kmax 比较：如果 x < kmax ，用 x 替换 kmax，然后更新堆（用时 log k）；否则不更新堆。

源代码如下：

#include <iostream>
#include <cstdlib>

#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * ((i) + 1))

using namespace std;

void Swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp; 
}

//此函数把一颗二叉树中以 node 为根的子树变成最大堆。
//注意: 使用的前提条件是 node 节点的左右子树(如果存在的话)都是最大堆。
void MaxHeapify(int heap[], int heap_size, int node) 
{
    int l_child = LEFT(node);
    int r_child = RIGHT(node);
    int max_value = node;
    if (l_child < heap_size && heap[l_child] > heap[max_value])
        max_value = l_child;
    if (r_child < heap_size && heap[r_child] > heap[max_value])
        max_value = r_child;
    if (max_value != node)
    {
        Swap(heap[node], heap[max_value]);
        // 之后还要保证被交换的子节点构成的子树仍然是最大堆
        // 如果不是这个节点会继续"下沉"，直到合适的位置
        MaxHeapify(heap, heap_size, max_value);
    }
}

void BuildMaxHeap(int heap[], int heap_size)
{
    if (heap_size < 2)
        return;
        
    int first_leaf = heap_size >> 1;   //first_leaf = heap_size / 2;
    int i;
    //从最后一个非叶子节点开始自底向上构建
    for (i = first_leaf - 1; i >= 0; i--)
        MaxHeapify(heap, heap_size, i); 
}

int main()
{
    int a[100];
    int i = 0;
    char ch;
    while((ch = cin.get()) != '\n')  //此处也可以用 cin.peek() ，只预读，不取出 
    {
        cin.unget();
        cin >> a[i++];
    }
    int k;
    cin >> k;
    BuildMaxHeap(a, k);
    for (int j = k; j < i; j++)
    {
        int KMAX = a[0];
        if (KMAX > a[j])
            Swap(a[0], a[j]);
        else 
            continue;
        MaxHeapify(a, k, 0);
    }
    for (int j = 0; j < k; j++)
        cout << a[j] << " ";
    cout << endl;
    return 0;
}

分析：这样下来，总的时间复杂度: O（k +（n - k）* log k）= O（n * log k） 。此方法得益于堆中进行查找和更新的时间复杂度均为： O（log k）（若使用解法二：在数组中找出最大元素，时间复杂度： O（k）） 。

特别注意：

• cin.peek() 只预读，不提取流数据，并且不会跳过空格和回车
• 还有一些更高效率的算法，并且也有一些可以提高上面算法的一些小的改进，有兴趣的可以看看下面的参考资料

参考资料：《编程之法》The Art of Programming By July
找最小的K个数