Как отсортировать 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 < п. Тогда ваша матрица выглядит так:
![a matrix with rows and columns sorted]()
Каждая окружность является матричной записью, и каждая стрелка указывает на известное отношение порядка (запись в источнике стрелки меньше, чем запись в пункте назначения стрелки).
Чтобы отсортировать матрицу, мы должны разрешить все неизвестные отношения порядка, некоторые из которых показаны в серых прямоугольниках здесь:
![the order relations remaining to be resolved]()
Сортировка всех этих блоков занимает:
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).