c - 从数组中找到 n 个最大的元素

Question

我有一个数组

A[4]={4,5,9,1}

我需要它给出前 3 个顶级元素，例如 9、5、4

我知道如何找到最大元素，但如何找到第二个和第三个最大值？

即如果

max=A[0]
for(i=1;i<4;i++)
{
  if (A[i]>max)
  {
    max=A[i];
    location=i+1;
  }
}

实际上排序不适合我的应用，因为，

位置编号对我来说也很重要，即我必须知道前 3 个最大值出现在哪个位置，这里是第 0、1 和 2 个位置……所以我在想一个逻辑

在获得最大值后，如果我可以将 0 放在那个位置并且可以对新数组应用相同的步骤，即 {4,5,0,1}

但是我有点困惑如何将我的逻辑放入代码中

Answer 1

考虑使用 Python 标准库中采用的技术。它使用底层堆 data structure :

def nlargest(n, iterable):
    """Find the n largest elements in a dataset.

    Equivalent to:  sorted(iterable, reverse=True)[:n]
    """
    if n < 0:
        return []
    it = iter(iterable)
    result = list(islice(it, n))
    if not result:
        return result
    heapify(result)
    for elem in it:
        heappushpop(result, elem)
    result.sort(reverse=True)
    return result

步骤是:

1. 制作一个 n 长度的固定数组来保存结果。
2. 用输入的前 n 个元素填充数组。
3. 将数组转换为 minheap .
4. 循环剩余的输入，如果新数据元素更大，则替换堆的顶部元素。
5. 如果需要，对最后的 n 个元素进行排序。

堆方法是内存高效的(不需要比目标输出更多的内存)并且通常比较次数非常少(参见 comparative analysis)。