TopK算法,用于寻找若干个数据中最大或最小的K个数。
实现TopK有两种方法，一种是基于快排的思想，一种是基于堆排的思想。
他们区别在于：
快排：时间复杂度O(n) 需要修改输入数组 不能处理海量数据，因为内存不够加载
堆排：时间复杂度O(nlogk) 不需要修改输入数组 可以处理海量数据
基于快排的TopK:
快排中最重要的一点就是Partition函数，Partition使pos左侧数据均小于num[pos],右侧均大于num[pos]。
如果我们要找数组的TopK，其实只要找到Partition返回分界K的那个点时，该位置pos右侧（或左侧）即满足要求。
如果某次Partition的返回值不等于分界点，则根据分界点与pos的关系继续Partition:
如果pos在k外，即pos包括的区间内有大于K的数据，则在pos+1和k间重新Partition
如果pos在k内，即pos包括的区间内的数据个数小于K,则在k和pos-1间重新Partition
class Solution
{
public:
void TopK_Qsort(vector<int>& arr,int k)
{
if(arr.empty()||arr.size()<=k)
return;
int pos=Partition(arr,0,arr.size()-1);
int addr=arr.size()-1-k+1;
while(pos!=addr)
{
if(pos<addr)
{
pos=Partition(arr,pos+1,addr);//当前区间过大，将旧区间减1后再在其中找分界点
}
else
{
pos=Partition(arr,addr,pos-1);//当前区间过小，将pos-1后再在其中找分界点
}
}
for(int i=pos;i<arr.size();i++)
cout<<arr[i]<<endl;
}
private:
int Partition(vector<int>& arr,int low,int high)
{
int tmp=arr[low];
while(low<high)
{
while(high>low&&arr[high]>=tmp)
high--;
arr[low]=arr[high];
while(low<high&&arr[low]<=tmp)
low++;
arr[high]=arr[low];
}
arr[high]=tmp;
return high;
}
};
基于堆排的TopK：
基于堆排的TopK思想很简单，以寻找最大的K个数为例：首先使用输入数组的前k个数构造一个小顶堆，然后从输入数组的第k+1个数开始，与小顶堆的根进行对比。
1)如果大于小顶堆的根，说明这个数比根更适合最大的K个数，则将小顶堆的根设置为这个新值，然后重新调整堆。
2)如果小于或等于小顶堆的根，说明这个数比根，也就是当前K个数里最小的一个相比没有优势，因此不用调整，进行下一个数的判断。
class Solution
{
public:
void TopK_Heap(vector<int>& arr,int k)
{
if(arr.size()<=k)
return;
vector<int> box;
box.resize(k);
for(int i=0;i<k;i++)
box[i]=arr[i];
for(int i=box.size()/2;i>=0;i--)
HeapAdjust(box,i);
for(int i=k;i<arr.size();i++)
{
if(arr[i]>box[0])
{
box[0]=arr[i];
HeapAdjust(box,0);
}
}
for(int i=0;i<box.size();i++)
cout<<box[i]<<endl;
}
private:
void HeapAdjust(vector<int>& nums,int pos)
{
for(int i=2*pos+1;i<nums.size();i=2*i+1)
{
if(i<nums.size()-1&&nums[i]>nums[i+1])
i++;
if(nums[i]>=nums[pos])
break;
swap(nums[i],nums[pos]);
pos=i;
}
}
};