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

Question

我最近参加了一次面试，被问到“编写一个程序，在10亿个数字的数组中找出最大的100个数字”。

我只能提供一种暴力解决方案，即在O(nlogn)的时间复杂度内对数组进行排序并取最后100个数字。

Arrays.sort(array);

面试官在寻求更好的时间复杂度，我尝试了几种其他的解决方案，但都无法回答他。是否有更好的时间复杂度解决方案？

- userx

---

也许问题在于它不是一个“分类”问题，而是一个“寻找”问题。 - geomagas

作为一份技术说明，排序可能不是解决这个问题的最佳方法，但我认为这不是暴力破解 - 我可以想到比这更糟糕的方法。 - Bernhard Barker

我刚刚想到了一个更加愚蠢的暴力方法……从这10亿个元素的数组中找出100个元素的所有可能组合，然后看哪个组合的总和最大。 - Shashank

请注意，所有确定性（和正确的）算法在这种情况下都是O(1)，因为没有维度增加。面试官应该问：“如何从一个长度为n的数组中找到m个最大的元素，其中n>>m？” - Bakuriu

可能是与从一亿个数字中检索前100个数字相同的问题。 - Adrian McCarthy

Answer 1

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

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

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

通常，如果你需要从N个数字集合中找出最大的K个数字，则复杂度为O(N log K)，而不是O(N log N)，当K与N相比非常小时，这可能非常重要。

---

这个优先队列算法的预期时间非常有趣，因为每次迭代都可能插入或不插入。

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

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

因此，插入的预期次数是：

预期运行时间可以表示为：

(k 次生成前 k 个元素的队列，然后进行 n-k 次比较，按照上述描述预期插入的次数，每次平均需要 log(k)/2 的时间)

需要注意的是，当 N 远大于 K 时，这个表达式更接近于 n 而不是 N log K。这在某种程度上是直观的，因为在问题的情况下，即使进行了 10,000 次迭代（相对于十亿来说很小），一个数字被插入到队列中的概率也非常小。

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

或者如果它们趋向于递减，则大多数最大的100个数字将非常早出现，我们的最佳运行时间基本上是 O(N + K log K)，当 K 远小于 N 时，它只是 O(N)。

---

注1：O(N)的整数排序/直方图

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

例如，计数排序在数字较小的情况下表现良好。16位数字只需要一个2^16计数器数组。而且，你可以在计数排序过程中构建的直方图中扫描，而不是实际扩展为排序后的数组。

在对数组进行直方图处理后，你可以快速回答任何顺序统计查询，例如前99个最大的数字，第200到100个最大的数字。32位数字会将计数散布在一个更大的数组或哈希表中，可能需要16 GiB的内存（每个2^32计数器需要4字节）。并且在真正的CPU上，可能会出现很多TLB和缓存未命中，而不像一个2^16元素的数组，L2缓存通常会命中。

同样地，基数排序在第一次遍历后只需查看顶部的桶。但是，常数因子可能仍然大于log K，具体取决于K。

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

如果您有更多数字，则可能需要64位计数器，将内存占用量加倍以初始化为零并进行随机访问。或者对于几个溢出16位或32位整数的计数器，需要一个哨兵值来指示其余计数器在其他位置（例如在小字典中，如映射到64位计数器的哈希表中）。

- Ron Teller

---

每次插入实际上只需要 O(100) 的时间复杂度。 - MrSmith42

@RonTeller，你不能高效地对链表进行二分查找，因此优先队列通常使用堆实现。如所描述的那样，插入时间复杂度为O(n)，而不是O(logn)。在Skizz让你产生怀疑之前，你第一次理解得是正确的（有序队列或优先队列）。 - Dev

十亿也是一个常数，因此如果是这种情况，则时间复杂度为 O(1) :P - Ron Teller

@RonTeller说，通常这类问题涉及到从数十亿个Google搜索结果中找到十个顶级页面，或者为词云找到最频繁的50个单词，或者在MTV上找到十首最受欢迎的歌曲等等。因此，在正常情况下，我相信可以安全地考虑k是常数且相对于n而言很小。但是，人们应该始终记住这种“正常情况”。 - ffriend

由于您有1G个项，随机采样1000个元素，并选择最大的100个。这样可以避免退化情况（已排序、逆序排序、大部分已排序），从而大大减少插入次数。 - ChuckCottrill

Answer 2

如果在面试中被问到这个问题，面试官可能想要看到你的解决问题的过程，而不仅仅是算法知识。

由于描述比较笼统，您可以询问面试官这些数字的范围或含义，以使问题更加明确。这样做可能会给面试官留下深刻的印象。例如，如果这些数字代表人的年龄，那么问题就变得容易得多了。通过合理的假设，即没有人活过200岁，您可以使用大小为200（也许201）的整数数组来计算具有相同年龄的人数，只需进行一次迭代即可。这里索引表示年龄。之后，找出100个最大的数字就轻而易举了。顺便提一下，这种算法称为计数排序。

无论如何，在面试中，使问题更具体和清晰对您都是有益的。

- jin

---

非常好的观点。没有其他人询问或表明有关这些数字的分布方式 - 这可能会影响如何解决问题。 - NealB

我很喜欢这个答案，以至于我想进一步扩展它。首先，读取数字一次以获取最小/最大值，以便您可以假设分布情况。然后，有两种选择。如果范围足够小，则构建一个数组，可以简单地在出现时勾选数字。如果范围太大，则使用上面讨论的排序堆算法...只是一个想法。 - Richard_G

我同意，向面试官反问问题确实会产生很大的影响。事实上，像“您是否受计算能力限制”这样的问题也可以帮助您通过使用多个计算节点并行化解决方案。 - Sumit Nigam

@R_G 不需要遍历整个列表。采样一小部分随机成员（例如一百万）足以获得有用的统计信息。 - Itamar

对于那些没有想到这种解决方案的人，我建议阅读计数排序 http://en.wikipedia.org/wiki/Counting_sort。这实际上是一个非常常见的面试问题：你能否以比O(nlogn)更好的效率对数组进行排序。这个问题只是一个扩展。 - Maxime Chéramy

Answer 3

你可以遍历数字，这需要 O(n) 的时间复杂度。

每当您找到一个比当前最小值大的值时，将新值添加到大小为 100 的循环队列中。

循环队列的最小值是您的新比较值。继续向该队列添加元素。如果已满，则从队列中提取最小值。

- Regenschein

---

这个不起作用。例如，查找{1,100,2,99}中的前2个最大数将返回{100,1}作为前2个最大数。 - Skizz

如果你不想每次都搜索整个队列找到下一个最小元素，那么你必须确保队列被排序。 - MrSmith42

部分排序，如堆排序，就足够了。请参考Ron Teller的回答。 - Christopher Creutzig

是的，我默默地假设一个提取最小队列被实现为堆。 - Regenschein

不要使用循环队列，而是使用大小为100的最小堆，它将在顶部具有至少一百个数字。相比较于队列需要O(n)的插入时间，这种方法只需要O(log n)的时间。 - techExplorer

Answer 4

我意识到这个标签是“算法”，但我会提供其他选项，因为它可能也应该被标记为“面试”。

这10亿个数字的来源是什么？如果是数据库，那么“select value from table order by value desc limit 100”就可以很好地完成工作 - 可能会有方言差异。

这是一次性的还是需要重复进行？如果需要重复进行，频率如何？如果是一次性的且数据在文件中，则“cat srcfile | sort (options as needed) | head -100”将让您快速地完成您获得报酬的轻松工作。

如果需要重复进行，建议选择任何合适的方法获取初始答案并存储/缓存结果，以便您能够不断地报告前100个。

最后，还有一个考虑因素。您正在寻找入门级工作，并与极客经理或未来的同事面试吗？如果是这样，您可以放弃所有描述相对技术优缺点的方法。如果您正在寻找更高级的管理工作，那么请像管理人员一样处理，关注解决方案的开发和维护成本，并说“非常感谢”，如果面试官想要专注于计算机科学的琐事，请离开。在那里，他和您都不太可能有太多的晋升机会。

祝您下次面试好运。

- Fred Mitchell

---

非常棒的回答。其他人都集中在这个问题的技术方面，而这个回应则涉及了商业社交方面。 - vbocan

我从未想过你会在面试中说声谢谢就离开而没有等待它结束。感谢你开拓了我的思路。 - UrsulRosu

为什么我们不能创建一个10亿元素的堆并提取100个最大元素。这样成本 = O(十亿) + 100 * O(log(十亿)) ?? - Mohit Shah

Answer 5

我的第一反应是使用堆，但也有办法在使用QuickSelect时不必将所有的输入值都保存在内存中。

创建一个大小为200的数组，并用前200个输入值填充它。运行QuickSelect并丢弃低100个值，这样就有了100个空位。读入接下来的100个输入值并再次运行QuickSelect。继续以100个一组地处理整个输入，直到处理完全部输入。

最终你会得到前100个数。如果有N个值，你需要大约运行N/100次QuickSelect。每个Quickselect的成本大约是某个固定常数的200倍，因此总成本是2N乘以某个常数。在我看来，这看起来是关于输入规模的线性级别，而无论我在本说明中硬编码的参数大小是100还是其他的。

- mcdowella

---

你可以加入一个小但可能很重要的优化：在对大小为200的数组进行快速选择（QuickSelect）分区后，我们已经知道前100个元素中的最小值。然后，在遍历整个数据集时，只有当当前值大于当前最小值时才填充下面100个值。这种算法的一个简单实现在C++中的性能与直接在由MT19937创建、均匀分布的200百万个32位int型数值数据集上运行的libstdc++'s partial_sort相当。 - dyp

好主意 - 不影响最坏情况分析，但值得做。 - mcdowella

值得一试，我会尝试的，谢谢！ - userx

这正是Guava的Ordering.greatestOf(Iterable, int)所做的。它绝对是线性时间和单遍扫描，而且是一个超级可爱的算法。我们还有一些实际的基准测试：在平均情况下，其常数因子略慢于传统的优先队列，但是这个实现对“最坏情况”输入（例如严格升序输入）更加抗过载。 - Louis Wasserman

Answer 6

你可以使用快速选择算法来找到排名在十亿减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所建议的那样：

使用堆（Heap）构建最大堆将花费O(N)的时间，然后前100个最大的数字将位于堆的顶部，你只需要从堆中取出这100个数字（100 X O(Log(N))）。

该算法的时间复杂度为：O(N) + 100 X O(Log(N)) = O(N)

- One Man Crew

---

您需要三次遍历整个列表。当1亿个整数大约有4GB时，如果无法将它们全部存入内存，该怎么办？在这种情况下，快速选择（quickselect）是最差的选择。我认为迭代一次并保持前100项的堆是O(n)性能最好的解决方案（请注意，由于堆中的n为100 = 常数 = 非常小，因此可以削减堆插入的O(log n)）。 - Thomas Jungblut

虽然时间复杂度仍为O(N)，但进行两次快速选择和另一个线性扫描的开销远远超出所需。 - Kevin

这是伪代码，所有解决方案都需要更多时间（O(NLOG(N)或100*O(N)）。 - One Man Crew

100*O(N)（如果语法有效）= O(100*N) = O(N)（尽管100可能是变量，所以这不是严格准确的）。哦，还有快速选择的最坏情况时间复杂度为O(N^2)（糟糕）。如果数据不适合内存，你将会从磁盘加载数据两次，这比一次更糟糕（这是性能瓶颈）。 - Bernhard Barker

@OneManCrew 这里的共识实际上是把问题搞错了，通过修改快速选择算法以选择预期高排名的枢轴，甚至可以将其运行在n(1+c)+o(n)次比较中，其中c可以任意小。 - mrip

Answer 7

尽管另一种快速选择的解决方案已被投票降级，但事实仍然存在：与使用大小为100的队列相比，快速选择将更快地找到解决方案。从比较的角度来看，快速选择的期望运行时间为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) 次比较。此外，使用快速选择算法能够更加高效，因为它会将数组中最大的100个元素留在右侧100个位置上。因此，实际的运行时间可以提高到2n + o(n)。

问题在于这是期望的运行时间，而不是最坏情况下的。但是通过使用一个合理的枢轴选择策略（例如，随机选择21个元素，并选择其中位数作为枢轴），比较次数可以保证以高概率不超过(2+c)n，其中c是任意小的常数。

事实上，通过使用优化的抽样策略（例如，随机抽取sqrt(n)个元素，选择第99个百分位数），可以将运行时间降低到(1+c)n + o(n)，其中c是任意小的常数（假设要选择的元素数量K是o(n)）。

另一方面，使用大小为100的队列将需要O(log(100)n)次比较，而100的对数近似等于6.6。

如果我们将这个问题看作是在大小为N的数组中选择前K个最大的元素，其中K=o(N)，但是K和N都增长到无穷大，那么快速选择版本的运行时间将是O(N)，队列版本的运行时间将是O(N log K)，因此从这个角度来看，快速选择也是渐进上优越的。

在评论中提到，对于随机输入，队列解决方案将在预期的时间内运行N + K log N。当然，除非问题明确说明，否则不可能假设输入是随机的。可以使队列解决方案以随机顺序遍历数组，但这将产生额外的代价：需要调用N次随机数生成器以及重新排列整个输入数组或者分配一个新的长度为N的数组来包含随机索引。

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

- mrip

---

你的最后一段是关键：拥有十亿个数字，将所有数据都保存在内存中或交换元素是不可行的。（至少这是我对问题的解释，假设这是一个面试题。） - Ted Hopp

在任何算法问题中，如果读取数据是一个问题，那么必须在问题中提到。这个问题陈述了“给定一个数组”，而不是“给定一个存储在磁盘上的数组，它不能适应内存并且不能根据冯·诺伊曼模型进行操作，该模型是算法分析的标准”。如今，您可以购买带有8GB RAM的笔记本电脑。我不确定将十亿个数字保存在内存中不可行的想法来自哪里。我现在在我的工作站上有数十亿个数字在内存中。 - mrip

快速选择的最坏情况指数级别地不可能发生，这意味着在实际应用中这是无关紧要的。可以很容易地修改快速选择算法，使得在高概率下比较次数为(2+c)n+o(n)，其中c可以任意小。 - mrip

“事实仍然是，与使用大小为100的队列相比，快速选择将更快地找到解决方案” - 不是这样的。堆解决方案需要约N + Klog（N）次比较，而快速选择平均需要2N次比较，中位数的中位数需要2.95次比较。对于给定的K，堆解决方案显然更快。 - Neil G

@NeilG 我想你是指 N + N log K。 - mrip

Answer 8

取出十亿个数中的前100个并进行排序。现在只需要遍历这十亿个数，如果源数大于前100个数中最小的数，则按顺序插入排序。最终得到的结果比集合大小为O(n)更接近。

- Samuel Thurston

---

抱歉，我没有看到比我自己更详细的答案。 - Samuel Thurston

取前500个数字，只有在列表填满时才停止排序（并且舍弃最低的400个数字）。 （不用说，如果新数字大于所选100个数字中的最低数字，则只将其添加到列表中。） - Hot Licks

如果它是均匀分布的，那么时间复杂度大约为O(N)。但是最坏情况下，如果数组是递增的，每次都需要插入到排序列表中，其中插入平均成本为K（例如InsertionSort的一步），则时间复杂度为O(N * K)。这就是为什么要使用带有堆的优先队列，使其变为O(N * log K)的原因。 - Peter Cordes

Answer 9

两种选择：

(1) 堆（优先队列）

维护一个大小为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) Map-reduce模型。

这与Hadoop中的单词计数示例非常相似。 Map任务：计算每个元素的频率或出现次数。 Reduce任务：获取前K个元素。

通常，我会给招聘者两个答案。给他们喜欢的那个。当然，编写map reduce代码可能会很费力，因为您必须知道每个确切参数。练习一下也无妨。 祝你好运。

- Chris Su

---

+1 for MapReduce，我不敢相信你是唯一一个在亿级数据中提到Hadoop的人。如果面试官要求处理千亿级别的数据呢？在我看来，你应该得到更多的赞同。 - Silviu Burcea

@Silviu Burcea 非常感谢。我也很重视MapReduce :) - Chris Su

虽然在这个例子中，100的大小是恒定的，但你应该将其通用化为一个单独的变量，即k。因为100和10亿一样是常数，那么为什么你给大量数字的大小变量n，而不是给小量数字呢？实际上，你的复杂度应该是O(nlogk)，而不是O(n)。 - Tom Heard

但我的观点是，如果你只是回答这个问题，10亿也是问题中固定的数字，那么为什么要将10亿泛化为n而不是将100泛化为k。按照你的逻辑，复杂度实际上应该是O(1)，因为在这个问题中，10亿和100都是固定的数字。 - Tom Heard

@TomHeard 好的。O(nlogk) 只有一个因素会影响结果。这意味着，如果 n 不断增加，"结果水平" 将呈线性增长。或者我们可以说，即使给出万亿个数字，我仍然可以得到最大的 100 个数字。然而，你不能说：随着 n 的增加，k 也在增加，从而导致 k 影响了结果。这就是为什么我使用 O(nlogk) 而不是 O(nlogn)。 - Chris Su

Answer 10

一个非常简单的解决方案是通过数组迭代100次来解决，这是O(n)复杂度。

每次取出最大的数字（并将其值更改为最小值，这样下一次迭代就不会看到它，或者通过跟踪先前答案的索引（通过跟踪索引，原始数组可以有多个相同的数字）来保持索引）。经过100次迭代，您就有了最大的100个数字。

- James Oravec

---

两个缺点 - (1) 在此过程中你破坏了输入 - 最好避免这种情况。(2) 你要多次遍历数组 - 如果该数组存储在磁盘上，无法放入内存，那么这比接受的答案慢近100倍是很容易的。(是的，它们都是O(n)，但仍然存在差异) - Bernhard Barker

不错的建议 @Dukeling，我增加了额外的措辞来避免通过跟踪先前答案索引来更改原始输入。这仍然很容易编码。 - James Oravec

一个O(n)解决方案的绝佳例子，比O(n log n)慢得多。log2(十亿)只有30... - gnasher729

@gnasher729 O(n log n) 中的常数有多大？ - miracle173