题目
输入n个整数，找出其中最小的k个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
分析
排序法
我们可以将这个整数数组先排序在取出前k个值就完成了题目要求。若题目要求不能修改原数组，这个时候我们还需要自己创建一个数组。这里只实现不能修改原数组的解法，排序函数用的是C库函数
C++
#include <iostream> #include <cstdlib> using namespace std; int compar_int(const void* a, const void* b) { /* 如果a > b，返回>0 如果a == b, 返回0 如果a < b，返回<0 */ return *(int*)a - *(int*)b; } void GetLeaseNumbers(int* n, int len,int* output, int k) { qsort(n, len, sizeof(n[0]), compar_int); for (int i = 0; i < len && i < k; ++i) { output[i] = n[i]; } } int main() { int n[] = { 4,5,1,6,2,7,3,8 }; int output[4]; GetLeaseNumbers(n, 8, output, 4); cout << "最小k个数为："; for (int i = 0; i < 4; ++i) { cout << output[i] << " "; } cout << endl; }
这个方法的复杂度取决于排序的算符复杂度,空间复杂度为O(1)
哈希表
我们用数组构建哈希表，时间复杂度会降到O(n)，但是空间复杂度为O(n)。最主要的问题就是我们构建多大一个数组合适呢。可能还有负数等等。所以就这里稍微提一提。我用一个标志记录的最大值，因为我们构建一个很大的数组，不用全部遍历完。
C++
#include <iostream> #include <cstdlib> using namespace std; void GetLeaseNumbers(int* n, int len,int* output, int k) { //假设没有负数 int tmp[100000] = { 0 }; int max = 0; for (int i = 0; i < len; ++i) { if (max < n[i]) max = n[i]; tmp[n[i]]++; } int j = 0; for (int i = 0; i < 100000 && i <= max && j < k; ++i) { while (tmp[i] > 0) { output[j++] = i; tmp[i]--; } } }
替换法
我们可以先拿出部分数据放到最小数组中，然后让之后的数据一个个与最小数组的最大值相比谁小留谁。这个方法就很好的解决了上面方法的问题。问题就转换为如何从数组中找最大值，然后比较替换。我们很容易想到最大堆。可以自己构建一个最大堆算法也可以直接用STL容器multiset(允许又重复值)。
C++
#include <iostream> #include <set> using namespace std; void GetLeaseNumbers(int* n, int len, int* output, int k) { multiset<int> set; int i = 0; for (i = 0; i < k; ++i)//初始化容器 { set.insert(n[i]); } multiset<int>::const_iterator it = set.begin(); //选拔环节 for (i = k; i < len; ++i) { it = set.end(); it--; if (*it > n[i]) { set.erase(*it - 1); set.insert(n[i]); } } it = set.begin(); for (int i = 0; i < k; ++i) { output[i] = *it; it++; } } int main() { int n[] = { 4,5,1,6,2,7,3,8 }; int output[4] = { 0 }; GetLeaseNumbers(n, 8, output, 4); cout << "最小k个数为："; for (int i = 0; i < 4; ++i) { cout << output[i] << " "; } cout << endl; }
本章完！
