给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组。
1.利用快排的partition函数来进行划分。如果我们的基准数划分完成了以后在第 k 位上的话，那基准数以及基准数前面的元素就是最小的k个数了。
2.创建一个大根堆，限定其最多只能放 𝑘k个元素。然后依次取待排序的数据 𝑎𝑟𝑟[𝑖] arr[i] 往堆里放，堆没满的话直接插入就可以了。如果堆满了的话，那目前堆顶元素就是堆中的最大值。这个时候我们来比较一下 𝑎𝑟𝑟[𝑖] arr[i] 和堆定元素的大小。
如果 𝑎𝑟𝑟[𝑖] arr[i] 比堆顶元素大的话，那就说明数据中已经有 𝑘k个元素比 𝑎𝑟𝑟[𝑖] arr[i] 小了。𝑎𝑟𝑟[𝑖] arr[i] 已经不可能属于最小的 𝑘k个数了。那就直接忽略掉 𝑎𝑟𝑟[𝑖]arr[i]继续看下一个数。
如果 𝑎𝑟𝑟[𝑖] arr[i] 比堆顶元素小的话，那就将堆顶元素删除，把 𝑎𝑟𝑟[𝑖] arr[i] 插入到堆中。
全部看完以后，堆里的k个元素就是最小的k个数了。
// // Created by RedmiBook on 2022/5/10. // #include <bits/stdc++.h> using namespace std; //解法1 快排解法 int partition(vector<int>&arr,int l,int r){ int rd = l+rand()%(r-l); swap(arr[rd],arr[l]); int key = arr[l]; while(l < r){ while(l < r && arr[r] >= key){ r--; } arr[l] = arr[r]; while(l < r && arr[l] < key){ l++; } arr[r] = arr[l]; } arr[l] = key; return l; } //解法2 快排解法 int partition2(vector<int>&arr,int l,int r){ int rd = l+rand()%(r-l); swap(arr[rd],arr[r]); int key = arr[r]; int i=l; for(int j=l;j<r;j++){ if(arr[j] < key){ swap(arr[j],arr[i]); i++; } } swap(arr[i],arr[r]); return i; } vector<int> GetLeastNumbers_Solution(vector<int>& input,int k){ vector<int>ans; int len = input.size(); if(k==0 || k>=len) {return ans;} int l=0,r=len-1; int mid = partition2(input,l,r); while(mid != k-1){ if(mid < k-1){ l = mid+1; mid = partition2(input,l,r); }else{ r = mid-1; mid = partition2(input,l,r); } } for(int i=0;i<k;i++){ ans.push_back(input[i]); } return ans; } //堆排序解法 vector<int> GetLeastNumbers_heap(vector<int>& input,int k){ vector<int> ans; int len = input.size(); if(k<0 || k>=len){return ans;} priority_queue<int> heap; for(int i=0;i<len;i++){ if(i < k){ heap.push(input[i]); }else{ if(input[i] < heap.top()){ heap.pop(); heap.push(input[i]); } } } for(int i=0;i<k;i++){ ans.push_back(heap.top()); heap.pop(); } return ans; } int main(){ srand(time(0)); //解法1 快排解法 vector<int> src; //4,5,1,6,2,7,3,8 src.push_back(4); src.push_back(5); src.push_back(1); src.push_back(6); src.push_back(2); src.push_back(7); src.push_back(3); src.push_back(8); vector<int>ans = GetLeastNumbers_heap(src,4); for(int i=0;i<ans.size();i++){ cout<<ans[i]<<" "; } return 0; }
