¿Cómo ordenar una matriz m x n que tiene todas sus m filas ordenadas y n columnas ordenadas?

Question

Dada una matriz con m filas yn columnas, cada una de las cuales está ordenada. ¿Cómo clasificar de manera eficiente toda la matriz?

sé una solución que se ejecuta en O (mn log (min (m, n)). Estoy en busca de una solución mejor.

El enfoque que sé básicamente toma 2 filas/cols a la vez y se aplica fusionar operación

Aquí se muestra un ejemplo:..

[[1,4,7,10], 

[2,5,8,11], 

[3,6,9,12]] 

es el Martix de entrada que tiene cada fila y columna ordenada

salida esperada es:

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

Otro ejemplo:

[[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

No creo que puede hacerlo más rápido que Ω (MN registro (min (m , n)), por lo menos no en el caso general.

Supongamos (sin pérdida de generalidad) que m < n. Luego, su matriz se ve así:

Cada círculo es una entrada de la matriz y cada flecha indica una relación de orden conocida (la entrada en la fuente de la flecha es menor que la entrada en el destino de la flecha)

Para ordenar la matriz, que debe resolver todas las relaciones de orden desconocidos, algunos de los cuales se muestran en los cuadros grises aquí:

Ordenación de todas estas cajas de toma:

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

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

= Ω (mn registro m)

Answer 2

Si los elementos son números enteros dentro de un cierto rango k, donde K = O (mn), podemos utilizar recuento tipo con espacio extra para alcanzar O (mn), de lo contrario el mnlog (min (m, n)) es lo mejor que podemos hacer.

Answer 3

Al crear un árbol de búsqueda binaria, podemos lograr esto en el tiempo O (mn). Tome el último elemento de la primera columna (elemento 3 en el ejemplo mencionado anteriormente), hágalo como raíz. Los nodos derechos serán los n mayores elementos de esa última fila y el nodo izquierdo será el elemento anterior, es decir. el (m-1) th o el 1er elemento de la segunda última fila. De manera similar para este elemento, los nodos correctos serán los n elementos de esa fila. De nuevo m-2 será el elemento de la izquierda y todos los n elementos en su fila serán los elementos correctos. Del mismo modo, avanzando, tendremos un árbol de búsqueda binaria creado en el tiempo O (mn). Esto es O (mn) porque no estamos buscando mientras insertamos, es una inserción simple al atravesar cambiando el puntero del nodo raíz. Luego se realizará el recorrido inorden de este BST, que también será el tiempo O (mn).