力扣

题意

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

法1—对数组进行排序

这个很容易想到，直接对原数组进行排序，再取出前k个元素返回即可。

class Solution {public:vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int> res;quick_sort(arr,0,arr.size()-1);while(k--){res.insert(res.begin(),arr[k]);}return res;}void quick_sort(vector<int>& arr,int l,int r){//递归出口，子数组长度为1时推出if(l>=r)return;int i=l,j=r;//以基准元素(arr[l])为中点，将数组arr划分成左右两个字数组while(i<j){//从右往左，查找第一个小于基准元素的元素while(i<j&&arr[j]>=arr[l])j--;//从左往右，查找第一个大于基准元素的元素while(i<j&&arr[i]<=arr[l])i++;//交换arr[i]和arr[j]swap(arr[i],arr[j]);}//让基准元素处于中点swap(arr[l],arr[i]);//递归处理左右子数组quick_sort(arr,l,i-1);quick_sort(arr,i+1,r);}};

法2—基于快速排序的数组划分

题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的k个数和其他数字两部分即可，而快速排序的哨兵划分可完成此目标。

根据快速排序原理，如果某次哨兵划分后基准数正好是第k+1小的数字，那么此时基准数左边的所有数字便是题目所求的最小的 k 个数。

根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于k，若true则直接返回此时数组的前k个数字即可。

算法流程：

getLeastNumbers() 函数：

若k大于数组长度，则直接返回整个数组；执行并返回quick_sort()即可；

quick_sort() 函数：

注意，此时quick_sort()的功能不是排序整个数组，而是搜索并返回最小的k个数。

1、哨兵划分：

划分完毕后，基准数为arr[i]，左 / 右子数组区间分别为[l, i - 1],[i + 1, r]；

2、递归或返回：

若k < i，代表第k+1小的数字在左子数组中，则递归左子数组；若 k>i，代表第k+1小的数字在右子数组中，则递归右子数组；若k=i，代表此时arr[k]即为第k+1小的数字，则直接返回数组前k个数字即可；

C++实现

class Solution {public:vector<int> getLeastNumbers(vector<int>& arr, int k) {if(k>=arr.size()){return arr;}return quick_sort(arr,k,0,arr.size()-1);}vector<int> quick_sort(vector<int>& arr,int k,int l,int r){int i=l,j=r;//以基准元素(arr[l])为中点，将数组arr划分成左右两个字数组while(i<j){//从右往左，查找第一个小于基准元素的元素while(i<j&&arr[j]>=arr[l])j--;//从左往右，查找第一个大于基准元素的元素while(i<j&&arr[i]<=arr[l])i++;//交换arr[i]和arr[j]swap(arr[i],arr[j]);}//让基准元素处于中点swap(arr[l],arr[i]);if(k>i)//最小的k个数在右子数组里面{return quick_sort(arr,k,i+1,r);}if(k<i)//最小的k个数在左子数组里面{return quick_sort(arr,k,l,i-1);}// k=i，此时arr[i]是第k+1个最小的元素，返回前k个元素即可vector<int> res(arr.begin(),arr.begin()+k);return res;}};

法3—利用大顶堆

建立一个大顶独，遍历数组中的元素，当堆中的元素个数小于k时，直接将元素插入到堆中；当堆中的元素个数等于k时，比较元素与堆顶的大小，如果比堆顶大，那么就跳过，继续遍历下一个元素，如果小于堆顶，就讲堆顶弹出，再将元素插入堆中。直到遍历完整个数组，当遍历完整个数组之后，堆中的元素就是最小的k个元素。

C++实现

class Solution {public:vector<int> getLeastNumbers(vector<int>& arr, int k) {if(k>=arr.size()){return arr;}if(k<=0)return {};vector<int>res;/*return quick_sort(arr,k,0,arr.size()-1);*/priority_queue<int> max_heap;for(int i=0;i<arr.size();++i){if(max_heap.size()<k)max_heap.push(arr[i]);else if(max_heap.size()==k){if(arr[i]<max_heap.top()){max_heap.pop();max_heap.push(arr[i]);}}}while(!max_heap.empty()){res.push_back(max_heap.top());max_heap.pop();}return res;}vector<int> quick_sort(vector<int>& arr,int k,int l,int r){int i=l,j=r;//以基准元素(arr[l])为中点，将数组arr划分成左右两个字数组while(i<j){//从右往左，查找第一个小于基准元素的元素while(i<j&&arr[j]>=arr[l])j--;//从左往右，查找第一个大于基准元素的元素while(i<j&&arr[i]<=arr[l])i++;//交换arr[i]和arr[j]swap(arr[i],arr[j]);}//让基准元素处于中点swap(arr[l],arr[i]);if(k>i)//最小的k个数在右子数组里面{return quick_sort(arr,k,i+1,r);}if(k<i)//最小的k个数在左子数组里面{return quick_sort(arr,k,l,i-1);}// k=i，此时arr[i]是第k+1个最小的元素，返回前k个元素即可vector<int> res(arr.begin(),arr.begin()+k);return res;}};