Найти n наибольших позиций элементов в 2D-массиве

Question

Как найти «n» наибольшие позиции элементов в 2D-массиве? Есть ли хороший алгоритм, кроме грубой силы?

Спасибо

Answer 1

Вы можете найти п наибольшие элементы (и их позиции) в двумерном массиве так же эффективно, как вы можете в один одномерный массив.

Есть a variety of selection algorithms, которые работают в линейном режиме. Quickselect имеет линейную среднюю временную сложность, но, как и Quicksort, может быть квадратичным в худшем случае. Алгоритм медианы медианов имеет ожидаемую и наихудшую линейную временную сложность.

Конечно, если элементы отсортированы, то это тривиально: перейдите в конец массива и выберите необходимое количество элементов оттуда. Это может занять небольшую логику в зависимости от того, как массив сортируется в двух измерениях, но это не сложно.