无需排序即可在数组中找到至少 10 个元素

Question

我需要在一个有 1000 个无序数的数组中找到最小的 10 个元素。 我首先想到的是：对其进行排序并选择前十个元素，但我的职责是在不排序的情况下做同样的事情。顺便说一句，我正在使用C编程。你能帮我吗？

Answer 1

使用最大大小为 10 的最大堆，您可以在

O(n * log(10) = O(n)

时间复杂度内实现此目的，如下所示：

1. 初始化最大堆，

   hp

   。
2. 将输入数组的前 10 个元素添加到堆中。
3. 迭代堆中的剩余元素，并对每个元素执行以下操作：

• 将该元素与堆顶端的元素进行比较。
• 如果较小，则从堆中弹出一个元素并将该元素推入堆上。

4. 在循环结束时，您将得到一个堆，其中包含输入数组的 10 个最小元素。堆顶端的元素是第十小的元素。退货吧。