c++ - 在二维数组中找到 n 个最大的元素位置

Question

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

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

Answer 1

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

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

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