【面试题030】最小的k个数
题目:
输入n个整数,找出其中最小的k个数。
例如输入4、5、1、6、2、7、3、8这8个字,则其中最小的4个数字是1、2、3、4。
思路一:
可以同样的基于随机快速排序的Partition函数,来对数组做划分,
基于k来作调整,返回调用Partition函数,直到左边的k个数字是整个数组中最小的k个数字。
ps.这种方法要修改数组中数字的顺序,因为Partition函数会调整数组中数字的顺序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
|
|
#include <iostream>
using namespace std;
void Swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; }
int Partition(int *numbers, int beg, int end) { //如果轴是随机取的话,这里得做一个Swap把这个轴元素交换到end位置 int small = beg - 1; int index; for (index = beg; index < end; ++index) { if (numbers[index] <= numbers[end]) { small++; Swap(&numbers[small], &numbers[index]); } } ++ small; Swap(&numbers[small], &numbers[end]); return small; }
void GetLeastNumbers(int *input, int n, int *output, int k) { if (input == NULL || output == NULL || k > n || n <= 0 || k <= 0) { return; } int start = 0; int end = n - 1; int index = Partition(input, start, end); while (index != k - 1) { if (index > k - 1) { end = index - 1; index = Partition(input, start, end); } else { start = index + 1; index = Partition(input, start, end); } } for (int i = 0; i < k; ++i) { output[i] = input[i]; }
}
int main() { int input[] = {4, 5, 1, 6, 2, 7, 3, 8}; int output[4]; int num = sizeof(input) / sizeof(input[0]); int k = sizeof(output) / sizeof(output[0]); GetLeastNumbers(input, num, output, k); for (int i = 0; i < k; ++i) { cout << output[i] << " "; } cout << endl; return 0; }
|
思路二:
遍历这n个数字,如果容器大小小于k,就放入。如果容器已经满了,则跟容器中的最大数字做比较,
如果大于最大数字,遍历下一个,如果小于当前已有的最大值,替换当前这个最大值。
如果用二叉树来实现这个容器,那么我们能在O(logk)
——我想到了最大堆,在O(1)时间内获得已有的k个数字中的最大值,但是需要O(logk)时间完成删除及插入操作。
我们可以利用红黑树来实现我们的容器,STL中set和multiset都是基于红黑树实现的。
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
|
|
#include <iostream> #include <set> #include <vector> using namespace std;
typedef multiset<int, greater<int> > intSet; typedef multiset<int, greater<int> >::iterator setIterator;
void GetLeastNumbers(const vector<int> &data, intSet &leastNumbers, int k) { leastNumbers.clear(); if ( k < 1 || (int)data.size() < k ) { return; }
vector<int>::const_iterator iter = data.begin(); for (; iter != data.end(); ++iter) { //有符号数/无符号数不匹配 if ((int)(leastNumbers.size()) < k) { leastNumbers.insert(*iter); } else { setIterator iterGreatest = leastNumbers.begin();
if (*iter < * (leastNumbers.begin())) { leastNumbers.erase(iterGreatest); leastNumbers.insert(*iter); } } } }
int main() { int input[] = {4, 5, 1, 6, 2, 7, 3, 8}; intSet leastNumbers; vector<int> data(&input[0], &input[7]); GetLeastNumbers(data, leastNumbers, 4);
while(!leastNumbers.empty()) { setIterator iterGreatest = leastNumbers.begin(); cout << *iterGreatest << " "; leastNumbers.erase(iterGreatest); }
cout << endl; return 0; }
|