Как отсортировать m x n-матрицу, которая отсортирована по всем m-строкам и n столбцам?

Question

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

Я знаю, что такое решение, которое работает в O (млн журнала (мин (т, п)). Я ищу лучшее решение.

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

Вот пример:..

[[1,4,7,10], 

[2,5,8,11], 

[3,6,9,12]] 

является входным Martix, который имеет все строки и столбца отсортированный

Ожидаемое выход:

[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

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

Пусть (без ограничения общности), что м < н. Тогда ваша матрица выглядит следующим образом:

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

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

Сортировка все коробки принимает:

2 Σ _{к < м} Ω (к журнал к) + (п - м + 1) Ω (м журнал м)

= 2 Ω (м ² журнал м) + (п - м + 1) Ω (м журнал м)

= Ω (млн журнал м)

Answer 2

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

Answer 3

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