输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
思路一：
使用一个大小为k的大根堆，遍历数组arr，遇到比根小的，则更新堆。最后大根堆里的数就是最小的k个数。
代码：
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
int l = arr.size();
if (l < k || k <= 0) {
return {};
}
priority_queue<int> q;
for(int i = 0;i < k;i++) {
q.push(arr[i]);
}
for(int i = k;i < l;i++) {
if (q.top() > arr[i]) {
q.pop();
q.push(arr[i]);
}
}
vector<int> ans;
for(int i = 0;i < k;i++) {
ans.push_back(q.top());
q.pop();
}
return ans;
}
};思路二：
把数组分成两部分，前半部分包含k个数，这k个数都小于下标为k的数，后半部分都大于下标为k的数。快速排序里有一部分就是刚好做这个工作。随机选择一个数random，把数组分成两部分，前半部分都小于random,后半部分都大于random,random的下标为index，如果index==k-1，则刚好找到答案。如果index小于k-1,说明答案在后半部分，如果index 大于k-1，则说明答案在前半部分。
代码：
class Solution {
public:
int randomPartion(vector<int>& arr,int l,int r) {
int randomIndex = rand()%(r-l+1) + l;
swap(arr[randomIndex],arr[r]);
int s = l-1;
for(int i = l;i < r;i++) {
if (arr[i] <= arr[r]) {
s++;
if(s != i) {
swap(arr[s],arr[i]);
}
}
}
s++;
swap(arr[s],arr[r]);
return s;
}
void partion(vector<int>& arr,int l,int r,int k) {
if (l >= r) {
return;
}
int pos = randomPartion(arr,l,r);
int num = pos - l + 1;
if (num == k) {
return;
}
else if( num < k) {
partion(arr,pos+1,r,k-num);
}
else {
partion(arr,l,pos-1,k);
}
}
vector<int> getLeastNumbers(vector<int>& arr, int k) {
int l = arr.size();
if (l < k || k <= 0) {
return {};
}
srand((unsigned)time(NULL));
partion(arr,0,l-1,k);
vector<int> ans;
for(int i = 0;i < k;i++) {
ans.push_back(arr[i]);
}
return ans;
}
};