这是排序的数组，并给出我们需要找到一种有效的方式前5个元素，我们不能对列表进行排序。

An unsorted array is given and we need to find top 5 elements in an efficient way and we cannot sort the list .

我的解决办法：

查找阵列中的最大元素。为O（n）

Find the max element in the array. O(n)

用它处理后删除这个最大元素/。

Delete this max element after processing/using it.

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

Repeat step 1 & 2 , k times ( 5 times in this case ).

时间复杂度： O（KN） / O（N），空间复杂度： O（1）

Time Complexity : O(kn) / O(n) , Space Complexity : O(1).

我想我们可以在 O（logN）的的最大因素，因此，它可以提高到 O（klogN）。请纠正我，如果我错了。

I think we can find the max element in O(logN) , So it can be improved to O(klogN). Please correct me if I am wrong.

我们可以做的比这更好的？使用最大堆将是低效的我猜？

Can we do better than this ? Using max-heap would be inefficient I guess?

PS - 这不是任何功课

PS - This is not any homework.

推荐答案

如果你可以使用一个辅助堆（最小堆与顶部负元素），你可以做，在O（nlogm），其中n是列表的长度和m最大元素的数量来跟踪。

If you can use an auxiliary heap (a min heap with minus element at top) you can do that in O(nlogm), where n is the list length and m the number of max elements to keep track of.

由于辅助堆中有一个固定的最大尺寸（5）我认为，该结构的操作可以被认为是O（1）。在这种情况下，复杂度为O（n）的

Since the aux heap has a fixed max size (5) I think that operations on that structure can be considered O(1). In that case the complexity is O(n).

伪code：

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)