在2D阵列中查找n个最大元素位置

Question

如何在2D阵列中查找'n'个最大元素位置？ 除了蛮力之外，还有一个好的算法吗？

谢谢

Answer 1

你可以尽可能有效，你可以找到一个二维数组n个最大元素（和它们的位置）的一维数组。

有线性时间运行的a variety of selection algorithms。 Quickselect具有线性平均时间复杂度，但像Quicksort一样，在最坏的情况下可以是二次方。中值中值算法具有预期和最坏情况下的线性时间复杂度。

当然，如果对元素进行排序，那么这很简单：转到数组的末尾，从中选择所需的元素数。这可能需要一些逻辑，这取决于数组如何在二维中排序，但这并不困难。