题目描述
- 输入n个整数,找出其中最小的K个数
- 例如,输入
4, 5, 1, 6, 2, 7, 3, 8
这 8
个数字,则最小的 4
个数字是 1, 2, 3, 4
题目解读
- 剑指Offer 209
- 可扩展为求最大的 k 个数
- 思路一、快速排序
- 思路二、时间复杂度为 O(n) 的算法,只有当我们可以修改输入的数组时可用
- 思路三、时间复杂度为 O(nlogk) 的算法,特别适合处理海量数据
代码
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int partion(vector<int>& input, int left, int right){
int povit = input[left];
while(left < right){
while(left < right && input[right] >= povit){
right --;
}
input[left] = input[right];
while(left < right && input[left] <= povit){
left ++;
}
input[right] = input[left];
}
input[left] = povit;
return left;
}
void QuickSort(vector<int>& input, int left, int right){
if(left < right){
int index = partion(input, left, right);
QuickSort(input, left, index-1);
QuickSort(input, index+1, right);
}
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
int len = input.size();
if(len <= 0 || k <= 0 || k > len){
return vector<int>();
}
QuickSort(input, 0, len-1);
vector<int> output;
for(int i=0; i < k; i++){
output.push_back(input[i]);
}
return output;
}
};
int main(){
int a[10] = {4, 5, 1, 6, 2, 7, 3, 8};
int len = 8;
int k = 4;
vector<int> input;
Solution ss;
for(int i=0; i < len; i++){
input.push_back(a[i]);
}
vector<int> output = ss.GetLeastNumbers_Solution(input, k);
for(int i=0; i < k; i++){
cout<<output[i]<<" ";
}
cout<<endl;
}
- 思路二、时间复杂度为 O(n) 的算法,只有当我们可以修改输入的数组时可用
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int partion(vector<int>& input, int left, int right){
int povit = input[left];
while(left < right){
while(left < right && input[right] >= povit){
right --;
}
input[left] = input[right];
while(left < right && input[left] <= povit){
left ++;
}
input[right] = input[left];
}
input[left] = povit;
return left;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> output;
int len = input.size();
if(len == 0 || k <= 0 || k > len){
return output;
}
int left = 0;
int right = len - 1;
int index = partion(input, left, right);
while(index != k-1){
if(index < k-1){
left = index + 1;
}
else{
right = index - 1;
}
index = partion(input, left, right);
}
for(int i=0; i < k; i++){
output.push_back(input[i]);
}
return output;
}
};
int main(){
int a[10] = {4, 5, 1, 6, 2, 7, 3, 8};
int len = 8;
int k = 4;
vector<int> input;
Solution ss;
for(int i=0; i < len; i++){
input.push_back(a[i]);
}
vector<int> output = ss.GetLeastNumbers_Solution(input, k);
for(int i=0; i < k; i++){
cout<<output[i]<<" ";
}
cout<<endl;
}
- 思路三、时间复杂度为 O(nlogk) 的算法,特别适合处理海量数据
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
int len = input.size();
vector<int> output;
set<int>::iterator it;
set<int> tt;
if(len <= 0 || k <= 0 || k > len){
return output;
}
for(int i=0; i < len; i++){
if(i < k){
tt.insert(input[i]);
}
else{
it = tt.end();
it--;
if(*it > input[i]){
tt.erase(it);
tt.insert(input[i]);
}
}
}
for(it = tt.begin(); it != tt.end(); it++){
output.push_back(*it);
}
return output;
}
};
总结展望
- 思路三虽然要慢一点,但它有两个明显的优点:
一是没有修改输入的数据(代码中的变量 input )。我们每次只是从 input 中读入数字,所有的写操作都是在容器 set 中进行的。
二是该算法适合海量数据的输入(包括百度在内的多家公司非常喜欢与海量输入数据相关的问题)。
假设题目是要求从海量的数据中找出最小的 k 个数字,由于内存的大小是有限的,有可能不能把这些海量的数据一次性全部载入内存。这个时候,我们可以从辅助存储空间(比如硬盘)中每次读入一个数字,根据查找比对容器中最大元素的方式判断是不是需要放入容器 set 即可。
这种思路只要求内存能够容纳leastNumbers即可,因此它最适合的情形就是n很大并且k较小的问题