编写一个程序，从10亿个数字的数组中找到最大的100个数字。

简单的解决方案是使用优先队列，将前100个数字添加到队列中，并跟踪队列中最小的数字，然后遍历其他十亿个数字，每次找到比优先队列中最大的数字更大的数字时，我们删除最小的数字，添加新数字，并再次跟踪队列中最小的数字。
如果数字是随机排序的，那么这个方法会很好用，因为当我们遍历十亿个随机数字时，下一个数字很少是已知的前100个数字之一。但是数字可能不是随机的。如果数组已按升序排序，则我们将始终向优先队列中插入元素。
因此，我们首先从数组中选择100,000个随机数字。为了避免可能会很慢的随机访问，我们添加了400个250个连续数字的随机组。通过这种随机选择，我们可以确信剩余的数字中很少有位于前100个数字之中，因此执行时间将非常接近于将十亿个数字与某个最大值进行简单比较的循环。

仅用一行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（标准库）对于这种问题非常方便。
注意：我并不是说这是最优解，但它可以拯救你的面试。

受@ron teller的回答启发，这里是一个简单的C程序，可以实现您想要的功能。

#include <stdlib.h>
#include <stdio.h>

#define TOTAL_NUMBERS 1000000000
#define N_TOP_NUMBERS 100

int 
compare_function(const void *first, const void *second)
{
    int a = *((int *) first);
    int b = *((int *) second);
    if (a > b){
        return 1;
    }
    if (a < b){
        return -1;
    }
    return 0;
}

int 
main(int argc, char ** argv)
{
    if(argc != 2){
        printf("please supply a path to a binary file containing 1000000000"
               "integers of this machine's wordlength and endianness\n");
        exit(1);
    }
    FILE * f = fopen(argv[1], "r");
    if(!f){
        exit(1);
    }
    int top100[N_TOP_NUMBERS] = {0};
    int sorts = 0;
    for (int i = 0; i < TOTAL_NUMBERS; i++){
        int number;
        int ok;
        ok = fread(&number, sizeof(int), 1, f);
        if(!ok){
            printf("not enough numbers!\n");
            break;
        }
        if(number > top100[0]){
            sorts++;
            top100[0] = number;
            qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function);
        }

    }
    printf("%d sorts made\n"
    "the top 100 integers in %s are:\n",
    sorts, argv[1] );
    for (int i = 0; i < N_TOP_NUMBERS; i++){
        printf("%d\n", top100[i]);
    }
    fclose(f);
    exit(0);
}

在我的电脑上（核心i3和快速SSD），它需要25秒钟，并进行1724次排序。我使用dd if=/dev/urandom/ count=1000000000 bs=1生成了一个二进制文件来运行此程序。
显然，每次只读取4个字节会存在性能问题-从磁盘读取，但这只是为了举例说明。好的一面是，几乎不需要内存。

 Although in this question we should search for top 100 numbers, I will 
 generalize things and write x. Still, I will treat x as constant value.

算法：从n中选择最大的x个元素

我将返回值称为LIST。它是x个元素的集合（在我看来应该是链表）

• 首先，从池中“按照它们的出现顺序”取出前x个元素，并将它们排序到LIST中（由于x被视为常数，因此这可以在常数时间内完成 - O(x log(x))时间）
• 对于每个接下来出现的元素，我们检查它是否大于LIST中最小的元素，如果是，则弹出最小值并将当前元素插入LIST中。由于这是有序列表，每个元素都应该在对数时间内找到其位置（二分搜索），由于它是有序列表，插入也不是问题。每个步骤也在常数时间内完成（O(log(x))时间）。

那么，最坏的情况是什么？

x log(x) + (n-x)(log(x)+1) = nlog(x) + n - x

所以最坏情况下的时间复杂度为O(n)。+1是检查数字是否大于LIST中最小的数字。平均情况下的预期时间取决于这些n个元素的数学分布。

可能的改进

这个算法可以针对最坏情况进行轻微改进，但在我看来（我无法证明这一点），这会降低平均行为。渐近行为将保持不变。
该算法的改进是，我们不会检查元素是否大于最小值。对于每个元素，我们将尝试插入它，如果它比最小值小，则将其忽略。虽然这听起来荒谬，但如果我们只考虑最坏情况，我们将有x log(x) + (n-x)log(x) = nlog(x)次操作。
对于这种用例，我没有看到任何进一步的改进。但你必须问自己-如果我需要做这个超过log(n)次并且对于不同的x呢？显然，我们会以O(n log(n))的时间对数组进行排序，并在需要时取出我们的x元素。

你可以在O(n)的时间内完成。只需遍历列表并跟踪你在任何给定点看到的100个最大数字和该组中的最小值。当你找到一个比你的十个最小数更大的新数字时，就替换它并更新你的100个最小值的新最小值（每次执行此操作可能需要100的固定时间，但这不会影响整体分析）。

最简单的解决方案是扫描这个十亿数字的大数组，并在一个小型数组缓冲区中保存迄今为止找到的100个最大值，而不进行任何排序，并记住该缓冲区的最小值。起初我认为这种方法是由fordprefect提出的，但在评论中他说他假设100个数字数据结构被实现为堆。每当发现一个新的比缓冲区中的最小值大的数字时，它将被新发现的值覆盖，并且再次搜索当前最小值的缓冲区。如果十亿数字数组中的数字是随机分布的，大多数情况下从大数组中获取的值会与小数组的最小值进行比较并被丢弃。只有在很小的一部分数字中，该值必须插入到小数组中。因此，可以忽略操作包含小数字的数据结构之间的差异。对于少量元素，很难确定使用优先队列是否比使用我的天真方法更快。
我想要估算在扫描包含10^9个元素的大数组时，小的100个元素的数组缓冲区中插入的次数。程序会扫描这个大数组的前1000个元素，并且最多需要在缓冲区中插入1000个元素。缓冲区包含扫描的1000个元素中的100个元素，也就是扫描到的元素的0.1。因此，我们假设从大数组中选择一个值大于当前缓冲区最小值的概率约为0.1，则该元素必须插入缓冲区。现在，程序扫描大数组的下一10 ^ 4个元素。由于每插入一个新元素，缓冲区的最小值都会增加，因此我们估计当前大于最小值的元素比例约为0.1，因此有1000个元素需要插入。实际上，插入到缓冲区的元素数量预计将更少。扫描这10 ^ 4个元素后，缓冲区中数字的分数将约为迄今为止扫描元素的0.01，因此在扫描接下来的10 ^ 5个数字时，我们假设不会插入超过0.01 * 10 ^ 5 = 1000个元素。继续这种推理方式，在扫描10 ^ 9个元素的大数组之后，我们插入了约7000个值。因此，在扫描包含10 ^ 9个随机大小元素的数组时，我们预计缓冲区中不会有超过10 ^ 4（= 7000四舍五入）个插入。每次向缓冲区插入一个元素后都必须找到新的最小值。如果缓冲区是一个简单的数组，则需要100次比较来找到新的最小值。如果缓冲区是另一种数据结构（例如堆），则至少需要1次比较才能找到最小值。要比较大数组的元素，我们需要10 ^ 9次比较。因此，总体而言，当使用数组作为缓冲区时，我们需要约10 ^ 9 + 100 * 10 ^ 4 = 1.001 * 10 ^ 9 次比较，使用其他类型的数据结构（例如堆）时至少需要1,000 * 10 ^ 9次比较。因此，如果性能由比较次数决定，使用堆只带来0.1％的收益。但是，在将元素插入具有100个元素的堆中并替换具有100个元素的数组并找到其新的最小值之间的执行时间有何差异？

• 在理论层面上：插入堆中需要多少比较。我知道它是O(log(n))，但常数因子有多大？

• 在机器层面上：缓存和分支预测对堆插入和数组线性搜索的执行时间有什么影响。

• 在实现层面上：由库或编译器提供的堆数据结构中隐藏了哪些额外的成本？

我认为在尝试估计100个元素堆和100个元素数组性能差异之前，必须回答这些问题。因此进行实验并测量实际性能是有意义的。

我看到很多关于O(N)的讨论，所以我提出了一些不同的想法来进行思考练习。
这些数字的性质是否已知？如果是随机的，那么就不要再往下看了，看看其他答案。你不会得到比他们更好的结果。
然而！看看填充列表的机制是否按照特定顺序填充该列表。它们是否按照明确定义的模式排列，以便您可以确定最大幅度的数字将在列表的某个区域或某个间隔中找到？可能存在某种模式。如果是这样的话，例如，如果它们保证处于某种正常分布中，具有中间的峰值，总是在定义的子集中重复上升趋势，在数据集的中间某个时间T有一个持续的高峰，例如内部交易或设备故障的发生，或者可能只是每N个数字就有一个“峰”，如在灾难后的力量分析中，您可以显着减少需要检查的记录数。

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

找出十亿个数字中的前100个最好使用具有100个元素的min-heap。
首先，用遇到的前100个数字来初始化min-heap。min-heap将在根（顶部）存储前100个数字中最小的数字。
现在，随着你继续处理其余的数字，只需将它们与min-heap的根（前100个数字中最小的数字）进行比较。
如果遇到的新数字大于min-heap的根，则用该数字替换根，否则忽略它。
作为新数字插入min-heap的一部分，堆中最小的数字将来到顶部（根）。
一旦我们遍历了所有数字，我们就会在min-heap中拥有最大的100个数字。

我写了自己的代码，不确定它是否符合“面试官”的要求。

private static final int MAX=100;
 PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);
        queue.add(array[0]);
        for (int i=1;i<array.length;i++)
        {

            if(queue.peek()<array[i])
            {
                if(queue.size() >=MAX)
                {
                    queue.poll();
                }
                queue.add(array[i]);

            }

        }

我已经用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]

计算 1 亿个元素大约需要 40 秒，所以我害怕去计算 10 亿个元素。不过公平地说，我使用的是最坏情况的输入（具有讽刺意味的是一个已经排序好的数组）。