Как отсортировать матрицу amxn, в которой отсортированы все m строк и n столбцов?

Question

Дана матрица с m строками и n столбцами, каждый из которых отсортирован. Как эффективно отсортировать всю матрицу?

Я знаю решение, которое работает в O (m n log (min (m, n))). Я ищу лучшее решение.

Подход, который я знаю, в основном занимает 2 строки / столбцы одновременно и применяет операцию слияния.

Вот пример:

[[1,4,7,10],

 [2,5,8,11],

 [3,6,9,12]]

- это входной мартикс, в котором отсортированы все строки и столбцы.

Ожидаемый результат:

[1,2,3,4,5,6,7,8,9,10,11,12]

Другой пример:

[[1, 2, 3, 3, 4, 5, 6, 6, 7, 7],

 [1, 2, 4, 6, 7, 7, 8, 8, 9,10],

 [3, 3, 4, 8, 8, 9,10,11,11,12],

 [3, 3, 5, 8, 8, 9,12,12,13,14]]

Answer 1

Я не думаю, что вы можете сделать это быстрее, чем Ω ( mn log (мин ( m , n )), по крайней мере, за общий случай.

Предположим (без ограничения общности), что m <<em> n . Тогда ваша матрица выглядит так:

Каждый кружок представляет собой матричную запись, и каждая стрелка указывает на известное отношение порядка (запись в источнике стрелки меньше, чем запись в пункте назначения стрелки).

Чтобы отсортировать матрицу, мы должны разрешить все отношения неизвестного порядка, некоторые из которых показаны здесь в серых полях:

Для сортировки всех этих ящиков требуется:

2 Σ _{k <<em> m} Ω ( k log k ) + ( n - м + 1) Ом ( м log м )

= 2 Ом ( м ² log м ) + ( n - м + 1) Ом ( м log m )

= Ω ( m n log m )

Answer 2

Создав бинарное дерево поиска, мы можем достичь этого за O (mn) времени. Возьмите последний элемент из первого столбца (элемент 3 в примере, упомянутом выше), сделайте его корнем. Правые узлы будут n большими элементами этой последней строки, а левый узел будет тем же элементом, что и выше. (m-1) -й или 1-й элемент из второго последнего ряда. Аналогично для этого элемента правые узлы будут n элементами этой строки. Снова m-2 будет левым элементом, а все n элементов в его строке будут правыми элементами. Точно так же, продвигаясь вперед, у нас будет двоичное дерево поиска, созданное за O (mn) время. Это O (mn), потому что мы не ищем во время вставки, это простая вставка при обходе путем сдвига указателя корневого узла. Затем будет выполнен обход этого BST по порядку, который также будет O (mn) время.

Answer 3

Если элементы являются целыми числами в пределах определенного диапазона k, где K = o (mn), мы можем использовать счетную сортировку с дополнительным пробелом для достижения O (mn), в противном случае mnlog (min (m, n)) является лучшимможно сделать.