TOP-k 问题
这道题如果要求时间复杂度优先可以考虑快排变形，如果空间复杂度优先，可以使用堆排。
下面给出了三种方法，第一种自己实现了一个堆结构，第二种用的stl的优先队列，第三种用了快排模板的变形。
堆的解决方法虽然速度不一定有快排快，但对于海量数据，本地不需要存储那么多数据
方法1：手写堆
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k)
{
if(k==0) return{};
//用数组的前k个数建立大根堆
heapify_build(arr,k-1);
//大根堆中维护当前最大的k个数
vector<int> res(arr.begin(),arr.begin()+k);
for(int i=0;i<res.size();i++)
{
cout<<res[i]<<endl;
}
for(int i=k;i<arr.size();i++)
{
// cout<<"--"<<endl;
// cout<<arr[i]<<" "<<res[0]<<endl;
//找一个比堆头小的数
if(arr[i]<res[0])
{
// cout<<"-"<<endl;
res[0]=arr[i];
heapify(res,k-1,0);
}
}
return res;
}
void heapify(vector<int>& nums,int n,int i)
{
int left=2*i+1;
int right=2*i+2;
int max=i;
if(left<=n&&nums[left]>nums[max]) max=left;
if(right<=n&&nums[right]>nums[max]) max=right;
if(max!=i)
{
swap(nums[max],nums[i]);
heapify(nums,n,max);
}
}
//建立一个大根堆
void heapify_build(vector<int>& nums,int n)
{
int start=(n-1)/2;
for(int i=start;i>=0;i--)
{
heapify(nums,n,i);
}
}
};
方法2：利用优先队列实现
#include<iostream>
using namespace std;
#include<vector>
#include<queue>
class Solution
{
public:
vector<int> smallestK(vector<int>& arr, int k)
{
if (k == 0) return{};
vector<int> res;
priority_queue<int, vector<int>, less<int>> q;
//用数组的前k个数建立大根堆
for (int i = 0; i < k; i++)
{
q.push(arr[i]);
}
//大根堆中维护当前最大的k个数
for (int i = k; i < arr.size(); i++)
{
//找一个比堆头小的数
if (arr[i] < q.top())
{
q.pop();
q.push(arr[i]);
}
}
for (int i = 0; i < k; i++)
{
res.push_back(q.top());
q.pop();
}
return res;
}
};
方法3：快排的变形
class Solution {
public:
vector<int> res;
vector<int> smallestK(vector<int>& arr, int k)
{
quick_sort(arr, 0, arr.size() - 1, k);
return res;
}
vector<int> quick_sort(vector<int> nums, int left, int right,int k)
{
if (left >= right)
return {};
//基准数一定要取出来
int i = left - 1, j = right + 1, x = nums[left + right >> 1];
while (i < j)
{
do i++; while (nums[i] < x);//找到一个>=x的数
do j--; while (nums[j] > x);//找到一个<=x的数
if (i < j)swap(nums[i], nums[j]);
}
//这时<=j 的都是<=x的 >=i的都是>=x的
//由于是要找最小的k个数 如果k是<=j的那么就只需要继续递归j的左边 反之同理
//这里要注意的是 <=j 实际上有j+1个数 所有k要跟j+1比较
if (k == j+1)
{
res.assign(nums.begin(), nums.begin() + k);
}
else if (k < j+1)
{
quick_sort(nums, left, j,k);
}
else if(k>j+1)
{
quick_sort(nums, j+1, right, k);
}
return res;
}
};