从数组中查找n个最大元素
我有一个arrays
A[4]={4,5,9,1} 我需要它会给出前3个顶级元素，如9,5,4
我知道如何找到最大元素，但如何找到第二和第三最大元素？
即如果
max=A[0] for(i=1;imax) { max=A[i]; location=i+1; } }
实际排序不适合我的应用程序，因为，
位置编号对我来说也很重要，即我必须知道前3个最大值出现在哪个位置，这里位于第0,1和2位……所以我在想逻辑
获得最大值之后如果我可以在该位置放置0并且可以对该新arrays应用相同的步骤，即{4,5,0,1}
但我有点困惑如何把我的逻辑放在代码中
考虑使用Python标准库中使用的技术。 它使用底层堆数据结构 ：
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
步骤是：
- 制作一个n长度的固定数组来保存结果。
- 使用输入的前n个元素填充数组。
- 将数组转换为minheap 。
- 循环其余输入，如果新数据元素较大，则替换堆的顶部元素。
- 如果需要，对最后的n个元素进行排序。
堆方法具有内存效率（不需要比目标输出更多的内存），并且通常具有非常少的比较（参见此比较分析 ）。
您可以使用选择算法
另外要提到的是复杂度为O（n），即O（n）用于选择，O（n）用于迭代，因此总数也是O（n）
你的本质要求相当于按降序排序数组。 最快的方法是使用heapsort或quicksort ，具体取决于arrays的大小。
一旦你的数组被排序，你的最大数字将在索引0，你的第二大数字将在索引1，….，一般来说你的第n个最大数字将在索引n-1
你可以参加这个程序，
1 。 将n个元素添加到另一个数组B[n] ;
2 。 对数组B[n]排序
3 。 然后对于A[n...m]检查中的每个元素，
A[k]>B[0]如果是，那么数字A[k]是n个大元素之中，所以，
在B[n]搜索A[k]正确位置，并替换并移动B[n]左边的数字，使B[n]包含n大元素。
4 。 对A[m]所有元素重复此操作。
最后， B[n]将具有n个最大元素。