https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
本题属于top k问题
方法一：快速排序
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
sort(arr.begin(),arr.end());
vector<int> result = {};
for(int i=0;i<k;++i){
result.push_back(arr[i]);
}
return result;
}
};
方法二：
我们用一个大根堆实时维护数组的前 kk 小值。首先将前 kk 个数插入大根堆中，随后从第 k+1k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。在下面的代码中，由于 C++ 语言中的堆（即优先队列）为大根堆，我们可以这么做。而 Python 语言中的对为小根堆，因此我们要对数组中所有的数取其相反数，才能使用小根堆维护前 kk 小值。
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int>vec(k, 0);
if (k == 0) return vec; // 排除 0 的情况
priority_queue<int>Q;
for (int i = 0; i < k; ++i) Q.push(arr[i]);
for (int i = k; i < (int)arr.size(); ++i) {
if (Q.top() > arr[i]) {
Q.pop();
Q.push(arr[i]);
}
}
for (int i = 0; i < k; ++i) {
vec[i] = Q.top();
Q.pop();
}
return vec;
}
};
复杂度分析：
由于使用了一个大小为 k 的堆，空间复杂度为;
入堆和出堆操作的时间复杂度均为，每个元素都需要进行一次入堆操作，故算法的时间复杂度为
。
方法三：快排思想
思路和算法
我们可以借鉴快速排序的思想。我们知道快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。
我们定义函数 randomized_selected(arr, l, r, k) 表示划分数组 arr 的 [l,r] 部分，使前 k 小的数在数组的左侧，在函数里我们调用快排的划分函数，假设划分函数返回的下标是 pos（表示分界值 pivot 最终在数组中的位置），即 pivot 是数组中第 pos - l + 1 小的数，那么一共会有三种情况：
如果 pos - l + 1 == k，表示 pivot 就是第 kk 小的数，直接返回即可；
如果 pos - l + 1 < k，表示第 kk 小的数在 pivot 的右侧，因此递归调用 randomized_selected(arr, pos + 1, r, k - (pos - l + 1))；
如果 pos - l + 1 > k，表示第 kk 小的数在 pivot 的左侧，递归调用 randomized_selected(arr, l, pos - 1, k)。
函数递归入口为 randomized_selected(arr, 0, arr.length - 1, k)。在函数返回后，将前 k 个数放入答案数组返回即可。
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;
}
};
自己的：
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> result(k,0);//initialize the result vector
priority_queue<int> q;
if(k==0) return result;
for(int i=0;i<k;++i){
q.push(arr[i]);
}
for(int i=k;i<arr.size();i++){
if(q.top()>arr[i]){
q.pop();
q.push(arr[i]);
}
}
for(int i=0;i<k;i++){
result[i]=q.top();
q.pop();
}
return result;
}
};
