algorithm - 未排序数组中的前 5 个元素

Question

给定一个未排序的数组，我们需要以有效的方式找到前 5 个元素，但我们无法对列表进行排序。

我的解决方案:

• 找到数组中的最大元素。 O(n)

• 处理/使用后删除此 max 元素。

• 重复步骤 1 和 2，k 次(在本例中为 5 次)。

时间复杂度:O(kn)/O(n)，空间复杂度:O(1)。

我认为我们可以在O(logN)中找到最大元素，所以可以改进为O(klogN)。如果我错了，请纠正我。

我们能做得更好吗？我猜使用最大堆会效率低下吗？

PS - 这不是任何作业。

Answer 1

如果你可以使用辅助堆(顶部有负元素的最小堆)，你可以在 O(nlogm) 中做到这一点，其中 n 是列表长度和 m 要跟踪的最大元素数。

由于辅助堆具有固定的最大大小 (5)，我认为对该结构的操作可以被视为 O(1)。在这种情况下，复杂度为 O(n)。

伪代码:

foreach element in list:
    if aux_heap.size() < 5  
        aux_heap.add(element)
    else if element > aux_heap.top()
        aux_heap.remove_top()
        aux_head.add(element)