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.

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

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

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

我知道这可能会被埋没，但这是我对一个基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甚至告诉你这样做，当你向下投票。

一个非常简单的解决方案是遍历该数组100次。也就是O(n)

每次取出最大的数字(并将其值更改为最小值，以便在下一个迭代中看不到它，或者跟踪以前答案的索引(通过跟踪索引，原始数组可以有多个相同的数字))。经过100次迭代，就得到了最大的100个数字。

你可以保留一个最大的100个数字的优先队列，遍历10亿个数字。每当遇到大于队列中最小数字(队列头)的数字时，删除队列头并将新数字添加到队列中。

用堆实现的优先级队列的插入+删除复杂度为O(log K).(其中K = 100，要查找的元素数量。N = 10亿，数组中元素的总数)。

在最坏的情况下，你得到十亿*log2(100)这比十亿*log2(十亿)对于O(N log N)基于比较的排序要好。

一般来说，如果你需要一组N个数字中最大的K个数字，复杂度是O(N log K)而不是O(N log N)，当K与N相比非常小时，这可能非常重要。

这种优先级队列算法的预期时间非常有趣，因为在每次迭代中可能会出现插入，也可能不会出现插入。

第i个数字插入队列的概率是一个随机变量大于同一分布中至少i- k个随机变量的概率(前k个数字自动添加到队列中)。我们可以使用顺序统计(见链接)来计算这个概率。

例如，假设这些数字是从{0,1}中均匀随机选择的，第(i-k)个数字(从i个数字中)的期望值为(i-k)/i，并且随机变量大于此值的概率为1-[(i-k)/i] = k/i。

因此，期望插入数为:

期望运行时间可表示为:

(k时间生成包含前k个元素的队列，然后是n-k个比较，以及如上所述的预期插入次数，每次插入的平均时间为log(k)/2)

注意，当N与K相比非常大时，这个表达式更接近于N而不是nlog K。这有点直观，就像在这个问题的情况下，即使经过10,000次迭代(与十亿次相比非常小)，一个数字被插入队列的机会也非常小。

但是我们不知道数组的值是均匀分布的。它们可能趋向于增加，在这种情况下，大多数或所有数字将成为所见最大的100个数字集合的新候选数。这个算法的最坏情况是O(N log K)

或者如果它们呈递减的趋势，最大的100个数字中的大多数将会非常早，我们的最佳情况运行时间本质上是O(N + K log K)对于K比N小得多的K，它就是O(N)

脚注1:O(N)整数排序/直方图

计数排序或基数排序都是O(N)，但通常有更大的常数因子，使它们在实践中比比较排序更差。在某些特殊情况下，它们实际上相当快，主要是对于窄整数类型。

例如，计数排序在数字很小的情况下表现良好。16位数字只需要2^16个计数器的数组。而不是实际展开到一个排序的数组，你可以扫描你建立的直方图作为计数排序的一部分。

在对数组进行直方图化之后，您可以快速回答任何顺序统计的查询，例如最大的99个数字，最大的200到100个数字)32位数字将计数分散到一个更大的数组或计数器哈希表中，可能需要16gib的内存(每个2^32个计数器4字节)。在真正的cpu上，可能会有很多TLB和缓存失误，不像2^16个元素的数组，L2缓存通常会命中。

类似地，Radix Sort可以在第一次传递后只查看顶部的桶。但常数因子仍然可能大于logk，这取决于K。

注意，每个计数器的大小足够大，即使所有N个整数都是重复的，也不会溢出。10亿略小于2^30，所以一个30位无符号计数器就足够了。32位有符号或无符号整数就可以了。

如果有更多的计数器，则可能需要64位计数器，初始化为零并随机访问需要占用两倍的内存。或者是少数溢出16或32位整数的计数器的哨兵值，以指示计数的其余部分在其他地方(在一个小字典中，例如映射到64位计数器的哈希表中)。

I would find out who had the time to put a billion numbers into an array and fire him. Must work for government. At least if you had a linked list you could insert a number into the middle without moving half a billion to make room. Even better a Btree allows for a binary search. Each comparison eliminates half of your total. A hash algorithm would allow you to populate the data structure like a checkerboard but not so good for sparse data. As it is your best bet is to have a solution array of 100 integers and keep track of the lowest number in your solution array so you can replace it when you come across a higher number in the original array. You would have to look at every element in the original array assuming it is not sorted to begin with.