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

Question

设 S 是一组存储在数组中的 n 个整数(不一定排序)。设计一种算法来查找 S 中的 10 个最大整数(通过创建一个长度为 10 的单独数组来存储这些整数)。您的算法必须在 O(n) 时间内完成。

我想我也许可以通过使用计数排序然后将最后 10 个元素添加到新数组中来回答这个问题。但显然这是错误的。有谁知道更好的方法吗？

Answer 1

方法一:您可以使用 FindMax() 算法在 O(N) 中找到最大数，如果您使用它 10 次:

10 * O(N) =O(N)

每次找到 max num 时将其放入新数组，下次使用 FindMax(); 时将忽略它

方法二:

您可以使用 Bubble 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)

方法三:

您可以使用最大堆:

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)