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

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

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

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

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

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

我看到了很多O(N)的讨论，所以我提出了一些不同的想法。

关于这些数字的性质有什么已知的信息吗?如果答案是随机的，那就不要再进一步了，看看其他答案。你不会得到比他们更好的结果。

However! See if whatever list-populating mechanism populated that list in a particular order. Are they in a well-defined pattern where you can know with certainty that the largest magnitude of numbers will be found in a certain region of the list or on a certain interval? There may be a pattern to it. If that is so, for example if they are guaranteed to be in some sort of normal distribution with the characteristic hump in the middle, always have repeating upward trends among defined subsets, have a prolonged spike at some time T in the middle of the data set like perhaps an incidence of insider trading or equipment failure, or maybe just have a "spike" every Nth number as in analysis of forces after a catastrophe, you can reduce the number of records you have to check significantly.

不管怎样，还是有一些值得思考的东西。也许这会帮助你给未来的面试官一个深思熟虑的回答。我知道，如果有人问我这样一个问题来回应这样的问题，我会印象深刻——这将告诉我，他们正在考虑优化。只是要认识到，优化的可能性并不总是存在的。

简单的解决方案是使用优先队列，将前100个数字添加到队列中，并跟踪队列中最小的数字，然后遍历其他10亿个数字，每当我们发现一个比优先队列中最大的数字大的数字时，我们删除最小的数字，添加新的数字，并再次跟踪队列中最小的数字。

如果这些数字是随机顺序的，这就很好了，因为当我们迭代10亿个随机数字时，下一个数字是目前为止最大的100个数字之一的情况是非常罕见的。但这些数字可能不是随机的。如果数组已经按升序排序，则始终向优先队列插入一个元素。

我们先从数组中选取100,000个随机数。为了避免可能很慢的随机访问，我们添加了400个随机组，每个组有250个连续的数字。通过这种随机选择，我们可以非常确定，剩下的数字中很少有进入前100位的，因此执行时间将非常接近于一个简单的循环，将10亿个数字与某个最大值进行比较。

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.

如果在面试中被问到这个问题，面试官可能想看你解决问题的过程，而不仅仅是你的算法知识。

The description is quite general so maybe you can ask him the range or meaning of these numbers to make the problem clear. Doing this may impress an interviewer. If, for example, these numbers stands for people's age then it's a much easier problem. With a reasonable assumption that nobody alive is older than 200, you can use an integer array of size 200 (maybe 201) to count the number of people with the same age in just one iteration. Here the index means the age. After this it's a piece of cake to find 100 largest numbers. By the way this algorithm is called counting sort.

无论如何，让问题更具体、更清楚对你在面试中是有好处的。

我知道这可能会被埋没，但这是我对一个基MSD的变化的想法。

伪代码:

//billion is the array of 1 billion numbers
int[] billion = getMyBillionNumbers();
//this assumes these are 32-bit integers and we are using hex digits
int[][] mynums = int[8][16];

for number in billion
    putInTop100Array(number)

function putInTop100Array(number){
    //basically if we got past all the digits successfully
    if(number == null)
        return true;
    msdIdx = getMsdIdx(number);
    msd = getMsd(number);
    //check if the idx above where we are is already full
    if(mynums[msdIdx][msd+1] > 99) {
        return false;
    } else if(putInTop100Array(removeMSD(number)){
        mynums[msdIdx][msd]++;
        //we've found 100 digits here, no need to keep looking below where we are
        if(mynums[msdIdx][msd] > 99){
           for(int i = 0; i < mds; i++){
              //making it 101 just so we can tell the difference
              //between numbers where we actually found 101, and 
              //where we just set it
              mynums[msdIdx][i] = 101;
           }
        }
        return true;
    }
    return false;
}

函数getMsdIdx(int num)将返回最高位(非零)的下标。函数getMsd(int num)将返回最高位。函数removeMSD(int num)将从一个数字中删除最有效的数字并返回该数字(如果删除最有效的数字后什么都没有留下，则返回null)。

完成后，剩下的就是遍历mynums以获取前100位数字。这大概是这样的:

int[] nums = int[100];
int idx = 0;
for(int i = 7; i >= 0; i--){
    int timesAdded = 0;
    for(int j = 16; j >=0 && timesAdded < 100; j--){
        for(int k = mynums[i][j]; k > 0; k--){
            nums[idx] += j;
            timesAdded++;
            idx++;
        }
    }
}

我需要注意的是，尽管上面的图看起来时间复杂度很高，但实际上它只有O(7*100)左右。

快速解释一下这是为了做什么: 从本质上讲，这个系统试图基于数字中数字的索引和数字的值来使用2d数组中的每个数字。它使用这些值作为索引来跟踪数组中插入了多少数值。当达到100时，它会关闭所有“较低的分支”。

这个算法的时间大概是O(十亿*log(16)*7)+O(100)。我可能是错的。此外，这很可能需要调试，因为它有点复杂，我只是把它写在我的头上。

编辑:没有解释的反对票是没有帮助的。如果你认为这个答案不正确，请留下评论。我很确定，StackOverflow甚至告诉你这样做，当你向下投票。