C++100w个数中找出最大的前K个数
/*100w个数中找出最大的前K个数*/
从网站建设到定制行业解决方案,为提供成都网站设计、成都网站建设、外贸网站建设服务体系,各种行业企业客户提供网站建设解决方案,助力业务快速发展。创新互联将不断加快创新步伐,提供优质的建站服务。
#include
using namespace std;
#include
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< if (i%5 == 0) { cout< } } cout< } 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个数
文章地址:http://myzitong.com/article/ghhhhe.html