一百万个数求前一百个

在内存有限的情况下，求出一百万个数的前一百个。

10年的天宁网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。全网营销推广的优势是能够根据用户设备显示端的尺寸不同，自动调整天宁建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。成都创新互联公司从事“天宁网站设计”,“天宁网站推广”以来，每个客户项目都认真落实执行。

解题思路：首先想到的是将一百万个数分成一百份，一份就是一万个，然后以一万建一个最小堆求出前一百个，一百份又是一万个这样就能求出前一百个；

代码如下：

#include

#include

#include

#include

#include

using namespace std;

const int N=10000;

const int K=100;

void CreateArray(vector&array)

{

srand(time(0));

array.reserve(N);

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

{

array.push_back(rand() % 10000);

}

for (size_t j = N-K; j < N; j++)

{

array[j] = rand()%N;

}

}

void AdjustDown(int* a, size_t size, int root)

{

int child = root * 2 + 1;

while (child < size)

{

if (child + 1

{

++child;

}

if (a[child] < a[root])

{

swap(a[child], a[root]);

root = child;

child = 2 * root + 1;

}

else

{

break;

}

}

}

void Gettop(vector&array)

{

int a[K] = {};

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

{

a[i] = array[i];

}

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

{

AdjustDown(a, K, i);

}

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

{

if (a[0]

{

a[0] = array[j];

AdjustDown(a, K, 0);

}

}

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

{

cout << a[i] << " ";

}

cout << endl;

}

void Test()

{

vectorarray;

CreateArray(array);

Gettop(array);

}

分享名称：一百万个数求前一百个
分享链接：http://bjjierui.cn/article/jpedho.html