C++100w个数中找出最大的前K个数

发布时间:2020-09-06 21:01:50 作者:zgw285763054
来源:网络 阅读:1252

/*100w个数中找出最大的前K个数*/

#include <iostream>

using namespace std;

#include <assert.h>


const int N = 10000;

const int K = 100;


void AdjustDown(int topK[], int size, size_t parent)

{

assert(topK);


int child = parent*2 + 1;


while (child < size)

{

if (child+1 < size

&& topK[child+1] < topK[child])

{

++child;

}


if (topK[child] < topK[parent])

{

swap(topK[child], topK[parent]);


parent = child;

child = parent*2 + 1;

}

else

{

break;

}

}

}


void GetTopKValue(int array[], int topK[])

{

assert(K < N);


for (int i = 0; i < K; ++i)

{

topK[i] = array[i];

}


//建小堆

for (int i = (K-2)/2; i >= 0; --i)

{

AdjustDown(topK, K, i);

}


for (int i = K; i < N; ++i)

{

if (array[i] > topK[0])

{

topK[0] = array[i];

AdjustDown(topK, K, 0);

}

}


for (int i = 0; i < K; ++i)

{

cout<<topK[i]<<" ";


if (i%5 == 0)

{

cout<<endl;

}

}


cout<<endl;

}


void Test()

{

int array[N] = {0};

int topK[K] = {0};


for (int i = 0; i < N; ++i)

{

array[i] = i;

}

array[9] = 111111;

array[99] = 1111111;

array[999] = 11111111;

GetTopKValue(array, topK);

}


int main()

{

Test();

return 0;

}

C++100w个数中找出最大的前K个数

推荐阅读:
  1. 找出N个数据中的最大的K个数据---堆排序
  2. 100万个数中找出最大的前K个数

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

数据结构 00

上一篇:iOS下border-image不起作用的解决办法

下一篇:Python定义二叉树及4种遍历方法实例详解

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》