Top K问题

written by dylan

Top K问题

找到数组中最大（最小）的K个数，例如7,6,3,5,2，Top3 的意思就是 找出最小的三个数即为：3,5,2.

解法1

讲数组从小到大进行排序，然后取出前K个数。

（先说最差的一个，为了引出后面的优化解法打铺垫）

解法2

利用堆来求解



所以代码就是在堆排序中做出稍微的修改即可以解决topk的问题.代码如下:

void adjustSort(int a[],int n,int i)
{
int father=i;
int child=2*i+1;
	while(child<n)
	{
		if(child<n-1&&a[child]<a[child+1])
		{
		child++;
		}
		if(a[child]>a[father])
		{
		swap(a[child],a[father]);
		father=child;
		child=2*father+1;
		}	
		else
		{
		break;
		}
	}
}
void topK(int a[],int k,int n)
{
for(int i=k/2-1;i>-0;i--)
	{
	adjustSort(a,k,i);
	}
for(int j=k;j<n;j++)//从第k+1开始进行比较
	{
		if(a[j]<a[0])
		{
		swap(a[j],a[0]);
		adjustSort(a,k,0);
		}
	}
}
int main()
{
int a[]={9,3,6,4,2};
topK(a,3,sizeof(a)/sizeof(a[0]));
for(int i=0;i<3;i++)
cout<<a[i]<<endl;
}

最优解-（快排+中位数bfprt）
https://blog.csdn.net/xiejitao/article/details/45721913