这个问题只需一行c++代码就可以用N log(100)的复杂度(而不是N log N)来回答。

 std::vector<int> myvector = ...; // Define your 1 billion numbers. 
                                 // Assumed integer just for concreteness 
 std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());

最终答案将是一个向量，其中前100个元素保证是数组中最大的100个数字，而其余元素是无序的

c++ STL(标准库)对于这类问题非常方便。

注意:我并不是说这是最佳的解决方案，但它可以挽救你的面试。

您可以使用快速选择算法在(按顺序)索引[十亿-101]处查找数字 然后遍历这些数字找出比这个数字更大的数。

array={...the billion numbers...} 
result[100];

pivot=QuickSelect(array,billion-101);//O(N)

for(i=0;i<billion;i++)//O(N)
   if(array[i]>=pivot)
      result.add(array[i]);

该算法时间为:2 X O(N) = O(N)(平均情况性能)

Thomas Jungblut建议的第二个选择是:

使用堆构建最大堆将花费O(N)，然后前100个最大的数字将在堆的顶部，所有你需要的是把它们从堆(100 X O(Log(N))。

该算法时间为:O(N) + 100 X O(Log(N)) = O(N)

你可以在O(n)个时间内完成。只需遍历列表，并跟踪在任何给定点上看到的最大的100个数字，以及该组中的最小值。当你发现一个新的数字大于你的10个数字中的最小值，然后替换它并更新你的新的100的最小值(可能每次你都要花100的常数时间来确定，但这并不影响整体分析)。

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

管理一个单独的列表是额外的工作，每次你找到另一个替代物时，你都必须在整个列表中移动东西。把它排序，选前100名。

我意识到这被标记为“算法”，但会抛出一些其他选项，因为它可能也应该被标记为“面试”。

10亿个数字的来源是什么?如果它是一个数据库，那么“从表中按值顺序选择值desc limit 100”就可以很好地完成工作-可能有方言差异。

这是一次性的，还是会重复发生?如果重复，频率是多少?如果它是一次性的，数据在一个文件中，那么'cat srcfile | sort(根据需要选择)| head -100'将让你快速完成有偿工作，而计算机处理这些琐碎的琐事。

如果重复，你会建议选择任何合适的方法来获得初始答案并存储/缓存结果，这样你就可以连续地报告前100名。

Finally, there is this consideration. Are you looking for an entry level job and interviewing with a geeky manager or future co-worker? If so, then you can toss out all manner of approaches describing the relative technical pros and cons. If you are looking for a more managerial job, then approach it like a manager would, concerned with the development and maintenance costs of the solution, and say "thank you very much" and leave if that is the interviewer wants to focus on CS trivia. He and you would be unlikely to have much advancement potential there.

祝你下次面试好运。