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元素的集合(在我看来应该是链表)

First x elements are taken from pool "as they come" and sorted in LIST (this is done in constant time since x is treated as constant - O( x log(x) ) time) For every element that comes next we check if it is bigger than smallest element in LIST and if is we pop out the smallest and insert current element to LIST. Since that is ordered list every element should find its place in logarithmic time (binary search) and since it is ordered list insertion is not a problem. Every step is also done in constant time ( O(log(x) ) time ).

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

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

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

可能的改进

在最坏的情况下，这个算法可以稍微改进，但恕我直言(我无法证明这一点)，这会降低平均行为。渐近行为是一样的。

该算法的改进在于，我们将不检查元素是否大于最小值。对于每个元素，我们将尝试插入它，如果它小于最小值，我们将忽略它。尽管如果我们只考虑我们将面临的最坏的情况，这听起来很荒谬

x log（x） + （n-x）log（x） = nlog（x）

操作。

对于这个用例，我没有看到任何进一步的改进。但是你必须问自己，如果我要对不同的x做多于log(n)次呢?显然，我们会以O(nlog (n))为单位对数组进行排序，并在需要时提取x元素。

我用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亿个元素。为了公平起见，我给它提供了最坏情况的输入(具有讽刺意味的是，一个已经排序的数组)。

此代码用于在未排序数组中查找N个最大的数字。

#include <iostream>


using namespace std;

#define Array_Size 5 // No Of Largest Numbers To Find
#define BILLION 10000000000

void findLargest(int max[], int array[]);
int checkDup(int temp, int max[]);

int main() {


        int array[BILLION] // contains data

        int i=0, temp;

        int max[Array_Size];


        findLargest(max,array); 


        cout<< "The "<< Array_Size<< " largest numbers in the array are: \n";

        for(i=0; i< Array_Size; i++)
            cout<< max[i] << endl;

        return 0;
    }




void findLargest(int max[], int array[])
{
    int i,temp,res;

    for(int k=0; k< Array_Size; k++)
    {
           i=0;

        while(i < BILLION)
        {
            for(int j=0; j< Array_Size ; j++)
            {
                temp = array[i];

                 res= checkDup(temp,max);

                if(res == 0 && max[j] < temp)
                    max[j] = temp;
            }

            i++;
        }
    }
}


int checkDup(int temp, int max[])
{
    for(int i=0; i<N_O_L_N_T_F; i++)
    {
        if(max[i] == temp)
            return -1;
    }

    return 0;
}

这可能不是一个有效的方法，但可以完成工作。

希望这能有所帮助

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.

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

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

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

 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元素的集合(在我看来应该是链表)

First x elements are taken from pool "as they come" and sorted in LIST (this is done in constant time since x is treated as constant - O( x log(x) ) time) For every element that comes next we check if it is bigger than smallest element in LIST and if is we pop out the smallest and insert current element to LIST. Since that is ordered list every element should find its place in logarithmic time (binary search) and since it is ordered list insertion is not a problem. Every step is also done in constant time ( O(log(x) ) time ).

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

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

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

可能的改进

在最坏的情况下，这个算法可以稍微改进，但恕我直言(我无法证明这一点)，这会降低平均行为。渐近行为是一样的。

该算法的改进在于，我们将不检查元素是否大于最小值。对于每个元素，我们将尝试插入它，如果它小于最小值，我们将忽略它。尽管如果我们只考虑我们将面临的最坏的情况，这听起来很荒谬

x log（x） + （n-x）log（x） = nlog（x）

操作。

对于这个用例，我没有看到任何进一步的改进。但是你必须问自己，如果我要对不同的x做多于log(n)次呢?显然，我们会以O(nlog (n))为单位对数组进行排序，并在需要时提取x元素。