查找数组n个最大元素 [英] Find n largest elements from an array

问题描述

我有一个数组

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

我需要它会给第3顶元素，如9,5,4

I need it would give the first 3 top elements like 9,5,4

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

I know how to find the max element but how to find the 2nd and 3rd max?

即如果

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

其实排序将不适合我的应用程序，因为

actually sorting will not be suitable for my application because,

位置编号也对我很重要，即我必须知道在哪个位置第3最大值发生，在这里它是在第0，第1和第2的位置......所以我想一个逻辑

the position number is also important for me i.e. I have to know in which positions the first 3 maximum is occurring, here it is in 0th,1th and 2nd position...so I am thinking of a logic

这让最大值后，如果我能在那个位置把0，并可能采用同样的步骤，新的阵列，即{4,5,0,1}

that after getting the max value if I could put 0 at that location and could apply the same steps for that new array i.e.{4,5,0,1}

但我有点困惑如何把我的逻辑在code

But I am bit confused how to put my logic in code

推荐答案

考虑使用Python标准库中所采用的技术。它采用底层堆数据结构：

Consider using the technique employed in the Python standard library. It uses an underlying heap 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 的元素进行排序。

1. Make an n length fixed array to hold the results.
2. Populate the array with the first n elements of the input.
3. Transform the array into a minheap.
4. Loop over remaining inputs, replacing the top element of the heap if new data element is larger.
5. If needed, sort the final n elements.

堆的方法是存储高效率（不需要比目标输出更多的内存），并且通常具有非常低的数目比较（见本对比分析）。

The heap approach is memory efficient (not requiring more memory than the target output) and typically has a very low number of comparisons (see this comparative analysis).

这篇关于查找数组n个最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！