这是谷歌或其他行业巨头提出的问题。也许下面的代码就是面试官想要的正确答案。 时间成本和空间成本取决于输入数组中的最大数量。对于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;
                        }
                    }
                }
            }
        }
    }
}

两个选择:

(1)堆(priorityQueue)

维护最小堆的大小为100。遍历数组。一旦元素小于堆中的第一个元素，就替换它。

InSERT ELEMENT INTO HEAP: O（log100）
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)

(2)映射-约简模型。

这与hadoop中的单词计数示例非常相似。 映射工作:计算每个元素出现的频率或次数。 减约:获取顶部K元素。

通常，我会给招聘人员两个答案。他们喜欢什么就给什么。当然，映射缩减编码会很费事，因为您必须知道每个确切的参数。练习一下也无妨。 祝你好运。

使用第n个元素得到第100个元素O(n) 迭代第二次，但只有一次，并输出大于此特定元素的所有元素。

请特别注意，第二步可能很容易并行计算!当你需要一百万个最大的元素时，它也会很有效。

你可以遍历这些数字，需要O(n)

只要发现一个大于当前最小值的值，就将新值添加到一个大小为100的循环队列中。

循环队列的最小值就是新的比较值。继续往队列中添加。如果已满，则从队列中提取最小值。

可能的改进。

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

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

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

我用Python写了一个简单的解决方案，以防有人感兴趣。它使用bisect模块和一个临时返回列表，它保持排序。这类似于优先级队列实现。

import bisect

def kLargest(A, k):
    '''returns list of k largest integers in A'''
    ret = []
    for i, a in enumerate(A):
        # For first k elements, simply construct sorted temp list
        # It is treated similarly to a priority queue
        if i < k:
            bisect.insort(ret, a) # properly inserts a into sorted list ret
        # Iterate over rest of array
        # Replace and update return array when more optimal element is found
        else:
            if a > ret[0]:
                del ret[0] # pop min element off queue
                bisect.insort(ret, a) # properly inserts a into sorted list ret
    return ret

使用100,000,000个元素和最坏情况输入是一个排序列表:

>>> from so import kLargest
>>> kLargest(range(100000000), 100)
[99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907,
 99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915,
 99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923,
 99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931,
 99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939,
 99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947,
 99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955,
 99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963,
 99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971,
 99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979,
 99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987,
 99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995,
 99999996, 99999997, 99999998, 99999999]

我花了40秒计算1亿个元素，所以我不敢计算10亿个元素。为了公平起见，我给它提供了最坏情况的输入(具有讽刺意味的是，一个已经排序的数组)。