algorithm - 在 100 个不同文件中查找前 10 个整数

Question

我是一个新人，正在准备面试。在我最近的采访中，我被问到一个问题，我找不到合适的答案。

我得到了大约 100 个文件，每个文件都包含大量逗号分隔的整数。我必须在整个文件中找到前 10 个整数。我尝试使用堆来解决它。但我对这个过程的时间复杂度感到困惑。任何帮助将不胜感激，谢谢。

score 1 · Accepted Answer

我认为您在使用堆数据结构方面走在了正确的轨道上。

您可以并行处理文件，并且可以为每个文件维护一个大小为 10 的最小堆。

当您遍历文件时，您将一个值插入到最小堆中，直到它已满（大小 10），然后对于位置 11 到 n 中的值

if current_value > min_heap.current()
    min_heap.extract()
    min_heap.insert(current_value)

您必须遍历 n 个值，最坏的情况是文件按升序排序。在这种情况下，您必须提取最小值并为位置 11 到 n 中的所有值插入一个新值。堆操作将是 O(log n)，为每个文件提供 O(n * log n) 的总体运行时间。

此时，您有 m（文件数）个最小堆，每个大小为 10。在这里，您可以使用最终最小堆来存储 m 个最小堆中包含的 10 个最大数字。此计算将是 O(m)，因为此时所有堆的最大大小为 10，这是一个常数。

总体而言，运行时间将为 O(n * log n + m)。m 可能比 n 小很多，所以在朋友中我们可以说 O(n * log n)。

即使你不并行执行第一步，它也会是 O(m * n * log n + m)，但如果 n 再次支配 m，我们可以说 O(n * log n)。

1 回答 1