在2D陣列中查找n個最大元素位置

Question

如何在2D陣列中查找'n'個最大元素位置？ 除了蠻力之外，還有一個好的算法嗎？

謝謝

Answer 1

你可以儘可能有效，你可以找到一個二維數組n個最大元素（和它們的位置）的一維數組。

有線性時間運行的a variety of selection algorithms。 Quickselect具有線性平均時間複雜度，但像Quicksort一樣，在最壞的情況下可以是二次方。中值中值算法具有預期和最壞情況下的線性時間複雜度。

當然，如果對元素進行排序，那麼這很簡單：轉到數組的末尾，從中選擇所需的元素數。這可能需要一些邏輯，這取決於數組如何在二維中排序，但這並不困難。