algorithm - 如何在 O(n) 中找到数组中的前 m 个最小整数？

Question

当数组的长度为 n 且 1 <= m <= n^0.5

我认为您可以使用选择算法来找到第 m 个最小的整数（在http://en.wikipedia.org/wiki/Selection_algorithm中有一个复杂的称为 BFPRT，即 O(n)），然后将其用作枢轴对数组进行分区以获得前 m 个最小整数。

但是，有没有办法使用诸如最小堆之类的数据结构来做到这一点？我怎么知道它是否是 O(n)？

score 4 · Accepted Answer

您可以在线性时间内创建一个最小堆。然后，您只需要以每次移除m的成本移除最小元素时间。log(n)那O(n) + m*O(log(n))就是O(n) + O(sqrt(n)*log(n))那就是O(n)。

编辑我最初说O(n) + O(sqrt(n)*log(n))的是O(sqrt(n)*log(n))这是错误的，因为O(n)实际上o(sqrt(n)*log(n))这意味着它不是O(sqrt(n)*log(n))

score 4 · Accepted Answer

4

只需使用基数排序在 O(n) 时间内对数组进行排序。

于 2013-04-16T08:00:41.267 回答

score 0 · Accepted Answer

Build_Heap(A) 方法可以在 O(n) 时间内从随机数组创建 min_heap 或 max_heap ，如果我们创建 min_heap 则需要 O(1) 时间来获取最小元素

所以获得最小元素的总时间是 O(n)+)(1) 即 O(n)

3 回答 3