在O(n)时间内找出数组中的10个最大整数

Question

假设有一个包含 n 个整数的数组 S（不一定排序），设计一个算法来查找 S 中前 10 个最大的整数（并将这些整数存储在一个长度为 10 的新数组中）。你的算法必须在 O(n) 时间内完成。

我曾尝试使用计数排序，然后将最后 10 个元素添加到新数组中来回答这个问题。但显然这是错误的。有没有人知道更好的方法？

- 101ldaniels

---

将新数组中的前10个数字相加。然后只需扫描剩余的元素并不断更新新数组。 - Abhishek Bansal

to easy, thank you! - 101ldaniels

等一下，我不确定这能行吗？ - 101ldaniels

可能是 https://zh.wikipedia.org/wiki/快速选择算法？ - mcdowella

Answer 1

方法1：您可以使用FindMax()算法，在O(N)中查找最大数字，如果您将其使用10次：

10 * O(N) =O(N)

每次找到最大的数后，将其放入新数组中，下次使用FindMax();时将忽略它。

方法2：

您可以使用冒泡排序10次：

1) Modify Bubble Sort to run the outer loop at most 10 times.
2) Save the last 10 elements of the array obtained in step 1 to the new array.

10 * O(N) =O(N)

方法三：

您可以使用 MAX 堆：

1) Build a Max Heap in O(n)
2) Use Extract Max 10 times to get 10 maximum elements from the Max Heap 10
* O(logn)

 O(N) + 10 * O(logN) = O(N)

- One Man Crew

Answer 2

使用 顺序统计 算法来查找第10大的元素。接下来，迭代数组以找到所有小于/等于它的元素。

时间复杂度：使用顺序统计的O(n) + 迭代一次数组的O(n) => O(n)。

- Saurav Sahu

---

在这种情况下的最坏情况几乎是O(N^2)。 - One Man Crew

@OneManCrew 在最坏情况下是O(n)。http://www.cse.ust.hk/~dekai/271/notes/L05/L05.pdf - Saurav Sahu

Answer 3

访问：

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

他们提到了六种方法。

- Yash Mehta

Answer 4

将它们插入到平衡二叉树中。O(N) + O(lg2 N)。

- jurhas