首页 > 试题广场 >

一亿个数找最大的1000个数，要求效率高占用内存少。函数原型

[问答题]

一亿个数找最大的1000个数，要求效率高占用内存少。函数原型为：find_max_data(int* source_data, int* max_data)，其中source_data是存放一亿个数的数组，max_data用于存放其中最大的1000个数。

推荐

tonywang

/* 基数排序  */
#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <algorithm>
#include <cassert>
#include "windows.h"
using namespace std;
#define MAXN 100000000 #define MAXM 1000
void find_max_data0( int dest[], int m, int src[], int n )
{
    fill( dest, dest + n, -INT_MAX );
    for ( int i = 0; i < n; i++ )
    {
        for ( int j = 0; j < m; j++ )
        {
            if ( src[i] > dest[j] )
            {
                dest[j] = src[i];
                break;
            }
        }
    }
}
void find_max_data1( int dest[], int m, int src[], int n )
{
    make_heap( src, src + n );
    for( int i = 0; i < m; i++ )
    {
        dest[i] = src[0];
        pop_heap( src, src + n-- );
    }
}
void radix_sort( int *src, int n )
{
    int *tmp = new int[MAXN];  int cnt[256];
    for( int i = 0; i < 4; i++ ) {
        memset( cnt, 0, sizeof(cnt) );
        for( int j = 0; j < MAXN; j++ )
        {
            cnt[ ( src[j] >> (8 * i) ) & 0xff ]++;
        }
        for ( int j = 1; j < 256; j++ )
        {
            cnt[j] = cnt[j - 1] + cnt[j];
        }
        for( int j = MAXN - 1; j >= 0; j-- )
        {
            tmp[ -- cnt[ ( src[j] >> (8 * i) ) & 0xff ] ] = src[j]; swap( src, tmp );
        }
    }
    delete [] tmp;
}
void find_max_data2( int dest[], int m, int src[], int n )
{
    radix_sort( src, n );
    int j = 0;
    for( int i = n - 1; i >= n - m; i-- )
    {
        dest[j++] = src[i];
    }
}
int src[MAXN];
int main()
{
    ( (unsigned int) time( NULL ) );
    src[i] = abs( i * 6516187 );
    DWORD t1, t2;
    t1  = GetTickCount();
    find_max_data2( dest2, MAXM, src, MAXN );  
    t2 = GetTickCount();
    printf( "find_max_data2 time cost:%dn", t2 - t1 ); 
    for( int i = 0; i < MAXM; i++ )
    {
        printf( "n" );  return 0;
    }
}

编辑于 2015-02-10 19:52:40 回复(1)

像我这么吊的下水道还有六个

// 从1亿个数中找到最大的1000个数
void find_max_data(int *source_data, int length, int k)
{
	int count = 0;
	
	multiset<int> set;
	multiset<int>::iterator it;
	for(int i = 0; i < length; i++)
	{
		if(count < k)
		{
			set.insert(source_data[i]);
		}
		else
		{
			it = set.begin();
			if(*it < source_data[i])
			{
				set.erase(it);
				set.insert(source_data[i]);
			}
		}
		count++;
	}
	it = set.begin();
	// 打印
	for (; it != set.end(); it++)
	{
		cout<<*it<<endl;
	}
}

编辑于 2015-07-30 19:58:11 回复(1)

易水

max_data数组存放source_data数组中前1000个数。

之后遍历1001到1亿，将每个数与max_data[999]比较，小则弃之，大的话，则使用插入排序法，放进去，并抛弃最小的一个。

发表于 2015-05-08 14:53:47 回复(1)

小盆友的问号增加了

这种情况当然是使用堆排序了，一次构造堆+999次重建堆，在一亿个元素的情况下时间复杂度接近o(n)

/*
一亿个数找最大的1000个数，要求效率高占用内存少。
*/
#include <array>
(2816)#include <algorithm>
using namespace std;

const int NUM_SET_SIZE = 100000000;
const int MAX_AMOUNT = 1000;

array<int, MAX_AMOUNT> find_max_data(array<int, NUM_SET_SIZE> num_set)
{
    array<int, MAX_AMOUNT> result;

    make_heap(num_set.begin(), num_set.end());   // 构造堆
    for (int i = 0; i < MAX_AMOUNT; i++)
        // 将last - 1处的值与first处进行交换，并使[first, last - 2]处成为一个有效堆
        pop_heap(num_set.begin(), num_set.end() - i);

    auto riter = num_set.rbegin();
    for (int i = 0; i < MAX_AMOUNT; i++)
        result[i] = *riter++;

    return result;
}

发表于 2020-03-18 14:45:11 回复(0)

李荣

<pre class="prettyprint lang-cpp">#include<iostream> #include<vector> using namespace std; #include<string.h> #include<assert.h> void down(int * data,int start,int end) { int i=start; int j=2*i+1; int temp= data[i]; while(j<=end) { if(j+1<end && data[j] >data[j+1]) j++; if(data[j] <temp) { data[i]=data[j]; i=j; j=2*i+1； } else { break; } } data[i]=temp; } void min_heap(int * data,int n) { for(int i=(n-1)/2;i>=0;i++) { down(data,i,n); } } void find_max_data(int* source_data,int * max_data) { memcpy(max_data,source_data,sizeof(int)*1000); //调整最小堆 min_heap(data,1000); for(i=1000;i<1000000000;i++) { int val = data[0]; if(data[0] <data[i]) { data[0]= data[i]; down(data,0,n); } } } void main() { find_max_heap(source_data,max_data); } </pre> <br />

发表于 2015-08-26 18:17:48 回复(0)

汤谷

很明显，max_data应该是一个最小堆，使用堆排序，只需部分排序，不需要全排，

(n-k)*log(k) 的时间复杂度。

编辑于 2015-08-03 16:55:24 回复(0)

xxj

插入排序

发表于 2014-11-07 10:38:22 回复(0)

提交观点

问题信息

C++工程师 C++ 迅雷 2014

来自：迅雷2014C++笔试卷A

上传者：雨过天晴

难度：

7条回答 52收藏 6886浏览

一亿个数找最大的1000个数，要求效率高占用内存少。函数原型

问题信息

热门推荐

相关试题