题目
输入n个数，找出其中最小的k个数。例如：输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4
分析
- 思路1
最简单的思路就是把输入的n个整数进行排序，排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度为O(nlogn)
vector<int> GetLeastNumbers(vector<int> input, int k) {
vector<int> result;
// 输入数组为空h，或者最小的k个数大于数组中元素个数
if (input.empty() || k > input.size())
return result;
// 数组排序
sort(input.begin(), input.end());
// 存储最小的k个数
for (int i = 0; i < k; i++)
result.push_back(input[i]);
return result;
}
- 思路2
基于Partition函数来解决这个问题，时间复杂度为O(n)。如果基于数组的第k个数字来调整，则使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）
// 快速排序
int Partition(vector<int>& input, int begin, int end) {
int low=begin;
int high=end;
int pivot=input[low];
while(low<high) {
while(low<high&&pivot<=input[high])
high--;
input[low]=input[high];
while(low<high&&pivot>=input[low])
low++;
input[high]=input[low];
}
input[low]=pivot;
return low;
}
vector<int> GetLeastNumbers2(vector<int> input, int k) {
int length=input.size();
// 容错处理
if(length==0||k>length) return vector<int>();
if(length==k) return input;
int start=0;
int end=length-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);
}
}
// 获取前面k个元素
vector<int> res(input.begin(), input.begin() + k);
return res;
}
- 思路3
可以先创建一个大小为k的数据容器来存储最小的k个数字，接下来每次从输入的n个整数中读入一个数。如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中，如果容器中已有k个数字，也就是容器满了，此时不能再插入新的数字而只能替换已有的数字。
找出这已有的k个数中的最大值，然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值。如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，那么就可以抛弃
因此，当容器满了之后，做3件事情：
- 一是在k个整数中找到最大值
- 二是有可能在这个容器中删除最大值
- 三是有可能插入一个新的数字
如果用一棵二叉树来实现这个数据容器，那么能在O(logk)时间内实现这3步操作。因此，对于n个输入数字而言，总的时间效率就是O(nlogk)。
因此可以使用红黑树实现
vector<int> GetLeastNumbers3(const vector<int> data, int k) {
// 容错处理
if (k < 1 || data.size() < k)
return vector<int>();
// 仿函数中的greater<T>模板，从大到小排序
multiset<int, greater<int>> leastNumbers;
// 得到
vector<int>::const_iterator iter = data.begin();
// 遍历数据源
for (; iter != data.end(); ++iter) {
if (leastNumbers.size() < k) { // 容器小于k个数就添加
leastNumbers.insert(*iter);
} else {
// 第一个元素是最大值
multiset<int, greater<int> >::iterator iterGreatest = leastNumbers.begin();
// 比较两个值
if (*iter < *(leastNumbers.begin())) {
leastNumbers.erase(iterGreatest); // 删除元素
leastNumbers.insert(*iter); // 插入元素
}
}
}
return vector<int>(leastNumbers.begin(), leastNumbers.end());
}
- 思路4
使用最大堆实现，时间效率是O(nlogk)
vector<int> GetLeastNumbers4(vector<int> input, int k) {
int length=input.size();
if(length<=0||k>length) return vector<int>();
// 得到前面k个数
vector<int> res(input.begin(),input.begin()+k);
// 建堆
make_heap(res.begin(),res.end());
// 开始遍历
for(int i=k;i<length;i++) {
if(input[i]<res[0]) {
// 先pop,然后在容器中删除
pop_heap(res.begin(),res.end());
res.pop_back();
// 先在容器中加入，再push
res.push_back(input[i]);
push_heap(res.begin(),res.end());
}
}
// 使其从小到大输出
sort_heap(res.begin(),res.end());
return res;
}
参考
《剑指offer》
最小的k个数
