寻找最小的 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个数
网友评论