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

Задана матрица с 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]]

Ответ 1

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

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

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

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

Сортировка всех этих блоков занимает:

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

= 2 Ω (m² log m) + (n - m + 1) Ω (m log m)

= Ω (m n log m)

Ответ 2

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

Ответ 3

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