维护一下最小堆,时间复杂度$O(nlogk)$,空间复杂度$O(k)$
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if(k == 0 ) return vector<int>();
priority_queue<int> q;
for(int & a : arr){
if(q.size() < k){
q.push(a);
}
else {
if(q.top() <= a) continue;
else{
q.pop();
q.push(a);
}
}
}
vector<int> res;
while(!q.empty()){
res.push_back(q.top());
q.pop();
}
return res;
}
};
QuickSelect 快速选择,和快排一样,只需要左半边就可以
时间复杂度 空间复杂度
抄的代码,还没开始研究
class Solution {
int partition(vector<int>& nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[r]);
return i + 1;
}
// 基于随机的划分
int randomized_partition(vector<int>& nums, int l, int r) {
int i = rand() % (r - l + 1) + l;
swap(nums[r], nums[i]);
return partition(nums, l, r);
}
void randomized_selected(vector<int>& arr, int l, int r, int k) {
if (l >= r) {
return;
}
int pos = randomized_partition(arr, l, r);
int num = pos - l + 1;
if (k == num) {
return;
} else if (k < num) {
randomized_selected(arr, l, pos - 1, k);
} else {
randomized_selected(arr, pos + 1, r, k - num);
}
}
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
srand((unsigned)time(NULL));
randomized_selected(arr, 0, (int)arr.size() - 1, k);
vector<int> vec;
for (int i = 0; i < k; ++i) {
vec.push_back(arr[i]);
}
return vec;
}
};