在二维数组中查找 n 个最大的元素位置

Question

如何在二维数组中找到“ n ”个最大元素位置？除了蛮力之外，还有没有好的算法？

任何建议都是有帮助的。
谢谢你。

Answer 1

您可以像在一维数组中一样高效地找到二维数组中的 n 个最大元素（及其位置）。

有多种在线性时间内运行的选择算法。Quickselect 具有线性平均时间复杂度，但与 Quicksort 一样，在最坏的情况下可能是二次的。中位数算法具有预期和最坏情况的线性时间复杂度。

当然，如果元素已排序，那么这很简单：转到数组的末尾并从那里选择所需数量的元素。这可能需要一些逻辑，具体取决于数组在二维中的排序方式，但这并不难。