编程题：最小的k个数算法,数据结构,堆排序TracelessLe的专栏-

题目：

输入n个整数，找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
输入示例：

[4,5,1,6,2,7,3,8], 4 

输出示例：

1, 2, 3, 4, 

规定：

需要对输入合法性进行校验。

解题思路：

思路：采用排序算法进行查找。三种方法：①普通排序（如冒泡排序），②快排，③堆排序。

（1）普通排序（此处采用冒泡排序）

注：由于题目只需找到最小的k个数，因此无需对所有元素进行排序，只需冒泡得到最小的k个元素即可。因此时间复杂度为O(kN)。

class Solution { public: void swap(vector<int> &input, int i, int j){ int temp = input[i];         input[i] = input[j];         input[j] = temp; }     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { //（1）最基础解法：冒泡，O(N^2)->O(kN) int length = input.size();//长度         vector<int> result; if(length==0 || k<=0||k>length){ return result; } for(int i=0;i<k;i++){ for(int j=i;j<length;j++){ if(input[i]>input[j]){//将最小的换到最左边，依次进行k次 swap(input,i,j); } } } for(int i=0;i<k;i++){             result.push_back(input[i]); } return result; } }; 

（2）快速搜索（快排思想）

注：由于题目只需找到最小的k个数，因此利用快排的哨兵来寻找，对所有元素遍历采用快排，直至哨兵index与k相等，左侧所有元素即为所求。因此时间复杂度为O(NlogN)。另外需要注意输入是否有重复元素，如果有重复元素则需要多做一些记录和判断。

①输入无重复元素时：

class Solution { public: void swap(vector<int> &input, int i, int j){ int temp = input[i];         input[i] = input[j];         input[j] = temp; }     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { //（2）升级解法：快排，O(NlogN) int length = input.size();//长度         vector<int> result; if(length==0 || k<=0||k>length){ return result; }         vector<int> input_copy = input;//复制，避免快排后原数组被修改 int pivot = 0;//哨兵index for(int i=0;i<length;i++){             input_copy = input;//复制，避免快排后原数组被修改 swap(input_copy, 0, i);//交换i与0的元素，固定哨兵pivot为数组第1个元素             pivot = 0;//哨兵index int pre = 1;//头 int beh = length-1;//尾 //快排 while(pre<=beh){//当pre超过beh后停止 if(input_copy[pre]>=input_copy[pivot]){ if(input_copy[beh]<input_copy[pivot]){//遇到等于的也跳过 swap(input_copy, pre, beh);                         pre++;                         beh--; } else beh--; } else pre++; } swap(input_copy, pre-1, pivot);             pivot = pre-1;//当pivot等于k时，左侧元素即为最小的k个数字 if(pivot==k-1){ for(int i=0;i<k;i++){                     result.push_back(input_copy[i]); } break;//跳出循环 } } return result; } }; 

②输入有重复元素时：

//改进：解决输入元素有重复的问题 class Solution { public: void swap(vector<int> &input, int i, int j){ int temp = input[i];         input[i] = input[j];         input[j] = temp; }     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { //（2）升级解法：快排，O(NlogN) int length = input.size();//长度         vector<int> result; if(length==0 || k<=0||k>length){ return result; }         vector<int> input_copy = input;//复制，避免快排后原数组被修改 int pivot = 0;//哨兵index for(int i=0;i<length;i++){             input_copy = input;//复制，避免快排后原数组被修改 swap(input_copy, 0, i);//交换i与0的元素，固定哨兵pivot为数组第1个元素             pivot = 0;//哨兵index int pre = 1;//头 int beh = length-1;//尾 //快排 int repet_cnt = 0; int pre_bak = 0; while(pre<=beh){//当pre超过beh后停止 if(input_copy[pre]==input_copy[pivot]){ if(pre_bak!=pre) repet_cnt++;                     pre_bak = pre;//保存上一次pre，避免重复计数 if(input_copy[beh]<input_copy[pivot]){ swap(input_copy, pre, beh);                         pre++;                         beh--; } else if(input_copy[beh]==input_copy[pivot]){ if(beh!=pre) repet_cnt++;                         beh--;//计数后beh前移 } else beh--; } else if(input_copy[pre]>input_copy[pivot]){ if(input_copy[beh]<input_copy[pivot]){//遇到等于的也跳过 swap(input_copy, pre, beh);                         pre++;                         beh--; } else beh--; } else pre++; } swap(input_copy, pre-1, pivot);             pivot = pre-1;//当pivot等于k时，左侧元素即为最小的k个数字 if(repet_cnt==0){ if(pivot==k-1){ for(int i=0;i<k;i++){                         result.push_back(input_copy[i]); } break;//跳出循环 } } else{ if(pivot==k-1){ for(int i=0;i<k;i++){                         result.push_back(input_copy[i]); } break;//跳出循环 } if(pivot+repet_cnt >=k-1){ for(int i=0;i<pivot;i++){                         result.push_back(input_copy[i]); } for(int i=pivot;i<k;i++){                         result.push_back(input_copy[pivot]); } break;//跳出循环 } } } return result; } }; 

（3）堆排序（完全二叉树）

注：由于题目只需找到最小的k个数，因此利用堆排序算法可以很好的求解，此处利用大顶堆。因此时间复杂度为O(NlogN)。

class Solution { public: void swap(vector<int> &input, int i, int j){ int temp = input[i];         input[i] = input[j];         input[j] = temp; } void heapify(vector<int>&input, int index, int length){ //堆化，构造大顶堆 int maxIndex = index; while(true){ if(input[index] < input[2*index+1] && (2*index+1)<length){ //与左子节点对比                 maxIndex = 2*index+1; } if(input[maxIndex] < input[2*index+2] && (2*index+2)<length){ //将最大值与右子节点对比                 maxIndex = 2*index+2; } if(index==maxIndex){ break;//无需交换 } swap(input, index, maxIndex);             index = maxIndex; } } void heap_sort(vector<int> &input, int length){ if(length<=1){ return; } //堆排序 for(int i=(length/2-1);i>=0;i--){ heapify(input,i, length); } }      vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { //（3）高级解法：堆排，O(NlogN) int length = input.size();//长度         vector<int> result; if(length==0 || k<=0||k>length){ return result; } heap_sort(input, length);//建堆并排序 //调换root和最后的节点元素，重新对剩余堆元素进行调整 int sorted_index = length-1; while(sorted_index!=0){ swap(input,0,sorted_index--);//交换最大值和尾部元素 heap_sort(input, --length);//对除去已排序的尾部元素后重新堆化，直至所有只剩一个元素时停止 } for(int i=0;i<k;i++){             result.push_back(input[i]); } return result; } }; 

完整程序：

#include <stdio.h> #include <vector> using namespace std; //code block，上述任一种方法的代码块，填充至此。 int main(){     vector<int> input = {4,5,1,6,2,7,3,8}; int k =4;     Solution so;     vector<int> result = so.GetLeastNumbers_Solution(input, k); int length = result.size(); for(int i =0; i<length;i++){ printf("%d, ",result[i]); } return 0; } 

输入输出测试：

测试用例1：
输入：
{4,5,1,6,2,7,3,8}, 4

输出：

测试用例2：
输入：
{2,2,1,2,2,7,3,8}, 4
输出：