如果不限定条件的话，这个问题还是很好解决的，但是当我们要求时间复杂度为O(N)，空间复杂度为O(1)时，问题就没那么好解决了。
简单的思路就是，创建一个大小为K=100的小堆，调整好，然后从K开始拿十万个数据一个一个跟堆头比较，如果比堆头大，就入堆，然后调整成最小堆，一直循环到第N=100000个数据。
计算
安全
数据库
网络和加速
企业服务
void AdjustDown(int* _a, size_t size,int i)
{
int parent = i;
int child = 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_t size,size_t n)
{
int* _a = new int[size];
for (int i = 0; i < size; i++)
{
_a[i] = a[i];
}
//建堆
for (int i = (size - 2) / 2; i >= 0; i--)
{
AdjustDown(_a, size,i);
}
for (int i = 0; i < n - size; i++)
{
if (_a[0] < a[size + i])
{
_a[0] = a[size + i];
AdjustDown(_a, size, 0);
}
}
return _a;
}
void _AdjustDown(int* a, size_t size, int i)
{
int parent = i;
int child = 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;
}
}
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
