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

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

我的解决方案：

• 找到数组中的最大元素。在）

• 处理/使用此最大元素后删除它。

• 重复步骤 1 和 2 k 次（本例中为 5 次）。

时间复杂度：O(kn) / O(n)，空间复杂度：O(1).

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

我们能做得比这更好吗？我猜使用最大堆效率很低？

PS - 这不是任何家庭作业。

如果您可以使用辅助堆（顶部带有负元素的最小堆），您可以在O(nlogm), where 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)