寻找最小的 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个数
