您好,登錄后才能下訂單哦!
在內(nèi)存有限的情況下,求出一百萬個(gè)數(shù)的前一百個(gè)。
解題思路:首先想到的是將一百萬個(gè)數(shù)分成一百份,一份就是一萬個(gè),然后以一萬建一個(gè)最小堆求出前一百個(gè),一百份又是一萬個(gè)這樣就能求出前一百個(gè);
代碼如下:
#include<windows.h>
#include<vector>
#include<ctime>
#include<cstdlib>
#include<iostream>
using namespace std;
const int N=10000;
const int K=100;
void CreateArray(vector<int>&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 <size && a[child + 1] < a[child])
{
++child;
}
if (a[child] < a[root])
{
swap(a[child], a[root]);
root = child;
child = 2 * root + 1;
}
else
{
break;
}
}
}
void Gettop(vector<int>&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]<array[j])
{
a[0] = array[j];
AdjustDown(a, K, 0);
}
}
for (size_t i = 0; i < K; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
void Test()
{
vector<int>array;
CreateArray(array);
Gettop(array);
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。