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

Question

给出了一个未排序的数组,我们需要以有效的方式找到前5个元素,我们无法对列表进行排序.

我的解决方案

• 找到数组中的max元素.上)

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

• 重复步骤1和2,k次(在这种情况下为5次).

时间复杂度:O(kn)/O(n),空间复杂度:O(1).

我想我们可以在O(logN)中找到max元素,因此可以将其改进为O(klogN).如果我错了,请纠正我.

我们能做得比这更好吗？我猜使用max-heap会效率低下吗？

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)