【数据结构】【面试题】找N个数据中最大的K个数据

如果不限定条件的话，这个问题还是很好解决的，但是当我们要求时间复杂度为O(N)，空间复杂度为O(1)时，问题就没那么好解决了。

简单的思路就是，创建一个大小为K=100的小堆，调整好，然后从K开始拿十万个数据一个一个跟堆头比较，如果比堆头大，就入堆，然后调整成最小堆，一直循环到第N=100000个数据。

voidAdjustDown(int*_a,size_tsize,inti)
{
intparent=i;
intchild=2*parent+1;
while(child<size)
{
//找出孩子中的最小值
if(child+1<size&&_a[child+1]<_a[child])
{
++child;
}
//与父节点做比较
if(_a[parent]>_a[child])
{
swap(_a[parent],_a[child]);
parent=child;
child=parent*2+1;
}
else
{
break;
}
}
}

//找N个数据中的最大K个
int*GetKTop(int*a,size_tn)
{
int*_a=newint[size];
for(inti=0;i<size;i++)
{
_a[i]=a[i];
}

//建堆
for(inti=(size-2)/2;i>=0;i--)
{
AdjustDown(_a,size,i);
}

for(inti=0;i<n-size;i++)
{
if(_a[0]<a[size+i])
{
_a[0]=a[size+i];
AdjustDown(_a,0);
}
}
return_a;
}

void_AdjustDown(int*a,inti)
{
intparent=i;
intchild=2*parent+1;
while(child<size)
{
//找出孩子中的最大值
if(child+1<size&&a[child]<a[child+1])
{
++child;
}
//拿父节点与最大子节点做比较
if(a[parent]<a[child])
{
swap(a[parent],a[child]);
parent=child;
child=2*parent+1;
}
else
{
break;
}
}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!