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元素。

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

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

我看到了很多O(N)的讨论，所以我提出了一些不同的想法。

关于这些数字的性质有什么已知的信息吗?如果答案是随机的，那就不要再进一步了，看看其他答案。你不会得到比他们更好的结果。

However! See if whatever list-populating mechanism populated that list in a particular order. Are they in a well-defined pattern where you can know with certainty that the largest magnitude of numbers will be found in a certain region of the list or on a certain interval? There may be a pattern to it. If that is so, for example if they are guaranteed to be in some sort of normal distribution with the characteristic hump in the middle, always have repeating upward trends among defined subsets, have a prolonged spike at some time T in the middle of the data set like perhaps an incidence of insider trading or equipment failure, or maybe just have a "spike" every Nth number as in analysis of forces after a catastrophe, you can reduce the number of records you have to check significantly.

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

虽然其他的quickselect解决方案已经被否决，但事实是quickselect将比使用大小为100的队列更快地找到解决方案。在比较方面，Quickselect的预期运行时间为2n + o(n)。一个非常简单的实现是

array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
  if(array[i]>r)
     add array[i] to result

这平均需要3n + o(n)次比较。此外，quickselect将数组中最大的100个项保留在最右边的100个位置，这可以提高效率。所以实际上，运行时间可以提高到2n+o(n)。

有一个问题是，这是预期的运行时间，而不是最坏的情况，但通过使用一个不错的主元选择策略(例如，随机选择21个元素，并选择这21个元素的中位数作为主元)，那么比较的数量可以保证高概率为(2+c)n对于任意小的常数c。

事实上，通过使用优化的抽样策略(例如随机抽样平方根(n)个元素，并选择第99百分位数)，对于任意小的c(假设K，要选择的元素数量为o(n))，运行时间可以降至(1+c)n + o(n)。

另一方面，使用大小为100的队列将需要O(log(100)n)个比较，log以2为底100的对数大约等于6.6。

如果我们从更抽象的意义上考虑这个问题，即从大小为N的数组中选择最大的K个元素，其中K=o(N)，但K和N都趋于无穷大，那么快速选择版本的运行时间将是o(N)，队列版本的运行时间将是o(N log K)，因此在这种意义上，快速选择也渐近地更好。

在注释中，提到队列解决方案将在随机输入的预期时间N + K log N内运行。当然，随机输入假设永远不会成立，除非问题明确地说明了这一点。队列解决方案可以以随机顺序遍历数组，但这将产生对随机数生成器的N次调用的额外成本，以及排列整个输入数组或分配一个长度为N的包含随机索引的新数组。

如果问题不允许您移动原始数组中的元素，并且分配内存的成本很高，因此不能复制数组，那就是另一回事了。但严格地从运行时间来看，这是最好的解决方案。

复杂度为O(N)

首先创建一个100个int的数组，将这个数组的第一个元素初始化为N个值的第一个元素， 用另一个变量CurrentBig来跟踪当前元素的索引

遍历N个值

if N[i] > M[CurrentBig] {

M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number)

CurrentBig++;      ( go to the next position in the M array)

CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.)

M[CurrentBig]=N[i];    ( pick up the current value again to use it for the next Iteration of the N array)

} 

完成后，从CurrentBig中打印M数组100次模100:-) 对于学生:确保代码的最后一行在代码退出之前没有胜过有效数据

两个选择:

(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元素。

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