题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
未完, 待续, 好像设计堆排序
先排序在遍历, 此处使用插曲排序
class Solution {
public:
void insertSort(vector<int> &vt) {
int inner = 0;
int outer = 0;
for (outer = 1; outer < vt.size(); outer++) {
int temp = vt[outer];
inner = outer;
while ((inner > 0) && (vt[inner-1] > temp)) {
vt[inner] = vt[inner - 1];
inner--;
}
vt[inner] = temp;
}
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> ret;
if ((0 > input.size()) || (0 >= k) || (k > input.size())) {
return ret;
}
insertSort(input);
for (int i = 0; i < k; i++) {
ret.push_back(input[i]);
}
return ret;
}
};
堆排序, 没看懂, 但感觉挺厉害的样子
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> result;
if(input.size()==0||k==0||k>input.size()){
return result;
}
for(int i=input.size()/2-1;i>=0;i--){//初始化堆
adjustHeap(input,i,k);
}
int i=k;
while(i<input.size()){
if(input[0]>input[i]){
int temp=input[i];
input[i]=input[0];
input[0]=temp;
adjustHeap(input,0,k);
i=k;
}else {
i++;
}
}
for(int i=0;i<k;i++){
result.push_back(input[i]);
}
return result;
}
void adjustHeap(vector<int>&input,int i,int length){//堆调整
int child=i*2+1;
if(child<length){
if(child+1<length&&input[child+1]>input[child]){
child=child+1;
}
if(input[child]>input[i]){
int temp=input[i];
input[i]=input[child];
input[child]=temp;
adjustHeap(input,child,length);
}
}
}
void heapSort(vector<int>&input,int length){//堆排序
for(int i=length/2-1;i>=0;i--){//初始化堆
adjustHeap(input,i,length);
}
for(int i=length-1;i>0;i--){
int temp=input[i];
input[i]=input[0];
input[0]=temp;
adjustHeap(input,0,i);
}
}
};