Recently I am adapting a theory that all the problems in the world could be solved with O(1). And even this one. It wasn't clear from the question what is the range of the numbers. If the numbers are it range from 1 to 10, then probably the the top 100 largest numbers will be a group of 10. The chance that the highest number will be picked out of the 1 billion numbers when the highest number is very small in compare to to 1 billion are very big. So I would give this as an answer in that interview.

首先取1000个元素并将它们添加到一个max堆中。现在取出前最多100个元素并将其存储在某个地方。现在从文件中选择接下来的900个元素，并将它们与最后100个最高的元素一起添加到堆中。

一直重复这个过程，从堆中取出100个元素，从文件中添加900个元素。

从100个元素中最后选出的100个元素将从10亿个数字中选出最大的100个元素。

求n个元素中最大的m个元素，其中n >>> m

最简单的解决方案，每个人都应该很明显，就是简单地做m次冒泡排序算法。

然后打印出数组的最后n个元素。

它不需要外部数据结构，并且使用了一种大家都知道的算法。

运行时间估计为O(m*n)。到目前为止最好的答案是O(nlog (m))，所以这个解决方案对于小m来说并不显着昂贵。

我并不是说这不能改进，但这是迄今为止最简单的解决方案。

可能的改进。

如果文件包含十亿的数字，读取它可能会很长…

为了提高工作效率，你可以:

将文件分成n个部分，创建n个线程，让n个线程在各自的部分中寻找最大的100个数字(使用优先级队列)，最后得到所有线程输出的最大的100个数字。 使用像hadoop这样的解决方案，使用集群来完成这样的任务。在这里，您可以进一步分割文件，并更快地输出10亿(或10^12)个数字的文件。

这是谷歌或其他行业巨头提出的问题。也许下面的代码就是面试官想要的正确答案。 时间成本和空间成本取决于输入数组中的最大数量。对于32位int数组输入，最大空间成本是4 * 125M字节，时间成本是5 *十亿。

public class TopNumber {
    public static void main(String[] args) {
        final int input[] = {2389,8922,3382,6982,5231,8934
                            ,4322,7922,6892,5224,4829,3829
                            ,6892,6872,4682,6723,8923,3492};
        //One int(4 bytes) hold 32 = 2^5 value,
        //About 4 * 125M Bytes
        //int sort[] = new int[1 << (32 - 5)];
        //Allocate small array for local test
        int sort[] = new int[1000];
        //Set all bit to 0
        for(int index = 0; index < sort.length; index++){
            sort[index] = 0;
        }
        for(int number : input){
            sort[number >>> 5] |= (1 << (number % 32));
        }
        int topNum = 0;
        outer:
        for(int index = sort.length - 1; index >= 0; index--){
            if(0 != sort[index]){
                for(int bit = 31; bit >= 0; bit--){
                    if(0 != (sort[index] & (1 << bit))){
                        System.out.println((index << 5) + bit);
                        topNum++;
                        if(topNum >= 3){
                            break outer;
                        }
                    }
                }
            }
        }
    }
}

此代码用于在未排序数组中查找N个最大的数字。

#include <iostream>


using namespace std;

#define Array_Size 5 // No Of Largest Numbers To Find
#define BILLION 10000000000

void findLargest(int max[], int array[]);
int checkDup(int temp, int max[]);

int main() {


        int array[BILLION] // contains data

        int i=0, temp;

        int max[Array_Size];


        findLargest(max,array); 


        cout<< "The "<< Array_Size<< " largest numbers in the array are: \n";

        for(i=0; i< Array_Size; i++)
            cout<< max[i] << endl;

        return 0;
    }




void findLargest(int max[], int array[])
{
    int i,temp,res;

    for(int k=0; k< Array_Size; k++)
    {
           i=0;

        while(i < BILLION)
        {
            for(int j=0; j< Array_Size ; j++)
            {
                temp = array[i];

                 res= checkDup(temp,max);

                if(res == 0 && max[j] < temp)
                    max[j] = temp;
            }

            i++;
        }
    }
}


int checkDup(int temp, int max[])
{
    for(int i=0; i<N_O_L_N_T_F; i++)
    {
        if(max[i] == temp)
            return -1;
    }

    return 0;
}

这可能不是一个有效的方法，但可以完成工作。

希望这能有所帮助