设 S 是一组存储在数组中的 n 个整数(不一定排序)。设计一种算法来查找 S 中的 10 个最大整数(通过创建一个长度为 10 的单独数组来存储这些整数)。您的算法必须在 O(n) 时间内完成。
我想我也许可以通过使用计数排序然后将最后 10 个元素添加到新数组中来回答这个问题。但显然这是错误的。有谁知道更好的方法吗？
最佳答案
方法一:
您可以使用 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)
关于arrays - 在 O(n) 时间内找到数组中的 10 个最大整数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39461975/