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

Question

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

我的解决方案：

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

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

• 重复步骤 1 和 2，k 次（在这种情况下为 5 次）。

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

我认为我们可以在O(logN)中找到最大元素，因此可以将其改进为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)

Answer 2

使用部分快速排序我们可以实现 O(n)，这不需要任何辅助空间。与其他解决方案一样，使用最大堆需要 O(n log k) 时间。