题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路整理
很简单的一题。基本思想就是排序，正好复习一下常用的排序算法。
- 快速排序
1）基本思想：快速排序是对冒泡排序的一种改进。其基本思想就是通过一趟排序将待排序序列分割为独立的两部分，其中一部分记录的关键字都比另一部分记录的关键字小，再分别对这两部分使用快排，直到整个序列有序为止。
2）时间复杂度：O(nlogn).
3）快速排序在所有时间复杂度为O(nlogn)的排序算法中，性能是最好的；
4）但是快排需要一个栈的辅助空间；
5）在初始待排序序列有序或基本有序的情况下，快排退化为冒泡排序，此时不适合用快排。
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(input.size()<k || k<=0) return vector<int>();
quickSort(input,k);
vector<int> res(input.begin(),input.begin()+k);
return res;
}
void quickSort(vector<int> &input,int k){
Qsort(input,0,input.size()-1,k);
}
void Qsort(vector<int> &input,int low,int high,int k){
if(low<high){
int vipot=Partition(input,low,high);
if(vipot>=k-1) Qsort(input,low,vipot-1,k); //如果左边记录已经达到k个，则只用对左边元素进行排序，不用管右边较大的记录
else{
Qsort(input,low,vipot-1,k);
Qsort(input,vipot+1,high,k);
}
}
}
int Partition(vector<int> &input,int low,int high){
int tmp=input[low];
while(low<high){
while(low<high && tmp<=input[high]) --high;
input[low]=input[high];
while(low<high && tmp>=input[low]) ++low;
input[high]=input[low];
}
input[low]=tmp;
return tmp;
}
};
- 堆排序
1）基本思想：通过将无序序列转换为堆，可以直接获得最小值或最大值，取出堆顶元素（最小值或最大值），令剩余的记录重新构建成堆，可以获得次小值或次大值，如此反复，可以获得一个有序序列。
2）时间复杂度：相比快速排序，堆排序在最坏的情况其时间复杂度也是O(nlogn);
3）堆排序只需要一个辅助记录空间；
4）堆排序的时间主要耗费在建初堆和反复调整堆的筛选上；
5）对于记录数比较少的序列，不适合用堆排序。
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(input.size()<k || k<=0) return vector<int>();
vector<int> res;
HeapSort(input,res,k);
return res;
}
void HeapSort(vector<int> &input,vector<int> &res,int k) {
int i;
for(i=input.size()/2;i>=0;--i){
HeapAdjust(input,i,input.size()-1);
}
int tmp;
for(i=input.size()-1;i>=0;--i){
res.push_back(input[0]); //每次将堆顶的最小记录放入结果集
if(res.size()==k) break; //获取到最小的k个记录后退出排序算法，避免超时
tmp=input[i];
input[i]=input[0];
input[0]=tmp;
HeapAdjust(input,0,i-1);
}
}
void HeapAdjust(vector<int> &input,int s,int m){ //筛选堆使其为最小堆
int tmp=input[s];
int i;
for(i=2*s+1;i<=m;i=2*i+1){
if(i+1<=m && input[i+1]<input[i]) ++i;
if(input[i]>=tmp) break;
input[s]=input[i];
s=i;
}
input[s]=tmp;
}
};
- 归并排序
1）基本思想：归并排序的基本思想就是将待排序序列分割为两个独立的部分，再依次对分的的两部分进行归并排序，之后再将二者合并；
2）时间复杂度：无论再最好情况下还是在最坏情况下，归并排序的时间复杂度都是O(nlogn);
3）归并排序是一种稳定的排序算法；
4）空间复杂度：O(n).显然归并排序不是就地排序。
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(input.size()<k || k<=0) return vector<int>();
MergeSort(input,0,input.size()-1,k);
vector<int> res(input.begin(),input.begin()+k);
return res;
}
void MergeSort(vector<int> &input,int low,int high,int k){
if(low<high){
int mid=(low+high)/2;
MergeSort(input,low,mid,k);
MergeSort(input,mid+1,high,k);
Merge(input,low,mid,high);
}
}
void Merge(vector<int> &input,int low,int mid,int high){
vector<int> res;
int i=low;
int j=mid+1;
while(i<=mid && j<=high){
if(input[i]<=input[j]){
res.push_back(input[i]);
++i;
}
else{
res.push_back(input[j]);
++j;
}
}
while(i<=mid){
res.push_back(input[i]);
++i;
}
while(j<=high){
res.push_back(input[j]);
++j;
}
for(i=0;i<res.size();++i){
input[low+i]=res[i];
}
}
};
- 优先级队列
优先级队列内部也是使用的堆排序技术，默认是构建大根堆，也就是优先级队列能始终保证队头元素最大，但是其内部不一定是完全有序的。
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(input.size()<k || k<=0) return vector<int>();
priority_queue<int,vector<int>,less<int> > q;
int i=0;
while(i<input.size()){
q.push(input[i]);
if(q.size()>k) q.pop();
++i;
}
vector<int> res;
while(!q.empty()){
res.push_back(q.top());
q.pop();
}
return res;
}
};
网友评论