Mediana de 5 matrices ordenadas

Estoy tratando de encontrar la solución para la mediana de 5 matrices ordenadas. Esta fue una entrevista de preguntas.

La solución en la que podía pensar era unir las 5 matrices y luego encontrar la mediana [O (l + m + n + o + p)].

Sé que para 2 matrices ordenadas del mismo tamaño podemos hacerlo en log (2n). [comparando la mediana de ambas matrices y luego arrojando 1 mitad de cada arreglo y repitiendo el proceso]. .. Encontrar la mediana puede ser un tiempo constante en matrices ordenadas … ¿así que creo que esto no es log (n)? ¿Cuál es la complejidad del tiempo para esto?

1] ¿Hay una solución similar para 5 matrices? ¿Qué pasa si las matrices son del mismo tamaño, entonces hay una mejor solución?

2] Supongo que, dado que se pidió 5, ¿habría alguna solución para N ordenamientos ordenados?

Gracias por cualquier puntero.

Algunas aclaraciones / preguntas que le hice al entrevistador:
Son las matrices de la misma longitud
=> No
Supongo que habría una superposición en los valores de matrices
=> Sí

Como ejercicio, creo que la lógica para 2 matrices no se extiende. Aquí hay una prueba:
Aplicando la lógica anterior de 2 matrices para decir 3 matrices: [3,7,9] [4,8,15] [2,3,9] … medianas 7,8,3
arroja elementos [3,7,9] [4,8] [3,9] .. medianas 7,6,6
arrojar elementos [3,7] [8] [9] ..medians 5,8,9 …
throw elements [7] [8] [9] .. median = 8 … ¿Esto no parece ser correcto?

La combinación de elementos ordenados => [2,3,4,7,8,9,15] => media esperada = 7

(Esta es una generalización de su idea para dos matrices).

Si comienzas mirando las cinco medianas de las cinco matrices, obviamente la mediana general debe estar entre la más pequeña y la más grande de las cinco medianas.

La prueba es algo así: si a es el mínimo de las medianas, y b es el máximo de las medianas, entonces cada conjunto tiene menos de la mitad de sus elementos menos de a y menos de la mitad de sus elementos mayores que b. El resultado sigue

Entonces en la matriz que contiene a, tirar números menos que a; en la matriz que contiene b, tirar números mayores que b … Pero solo tirar la misma cantidad de elementos de ambas matrices.

Es decir, si a es j elementos desde el comienzo de su matriz, yb es k elementos del final de su matriz, tiras los primeros elementos min (j, k) de una matriz y el último mínimo (j, k ) elementos de la matriz de b.

Itera hasta que tenga 1 o 2 elementos en total.

Cada una de estas operaciones (es decir, encontrar la mediana de una matriz ordenada y arrojar k elementos desde el inicio o el final de una matriz) es un tiempo constante. Entonces cada iteración es tiempo constante.

Cada iteración elimina (más de) la mitad de los elementos de al menos una matriz, y solo puede hacer ese registro (n) veces para cada una de las cinco matrices … Entonces el algoritmo general es log (n).

[Actualizar]

Como señala Himadri Choudhury en los comentarios, mi solución es incompleta; hay muchos detalles y casos de esquina de los que preocuparse. Entonces, para aclarar un poco las cosas …

Para cada una de las cinco matrices R, defina su “mediana inferior” como R [n / 2-1] y su “mediana superior” como R [n / 2], donde n es la cantidad de elementos en la matriz (y matrices) están indexados desde 0 y divididos por 2 rondas abajo).

Deje que “a” sea la más pequeña de las medianas inferiores, y “b” sea la más grande de las medianas superiores. Si hay múltiples matrices con la mediana inferior más pequeña y / o matrices múltiples con la mediana superior más grande, elija ayb de diferentes matrices (este es uno de esos casos de esquina).

Ahora, tomando prestada la sugerencia de Himadri: borre todos los elementos hasta e incluyendo a de su matriz, y todos los elementos hasta e incluyendo b de su matriz, teniendo cuidado de eliminar la misma cantidad de elementos de ambas matrices. Tenga en cuenta que a y b podrían estar en la misma matriz; pero si es así, no podrían tener el mismo valor, porque de lo contrario hubiéramos podido elegir uno de ellos de una matriz diferente. Por lo tanto, está bien si este paso termina tirando elementos desde el inicio y el final de la misma matriz.

Itera siempre que tenga tres o más matrices. Pero una vez que se reduce a una o dos matrices, debe cambiar su estrategia para que sea exclusiva en lugar de inclusiva; solo borra hasta pero no incluye a y hasta, pero no incluye b. Continúa así siempre que las dos o las dos matrices restantes tengan al menos tres elementos (lo que garantiza que progreses).

Finalmente, reducirá a unos pocos casos, el más complicado de los cuales son dos matrices restantes, una de las cuales tiene uno o dos elementos. Ahora, si te pregunto: “Dada una matriz ordenada más uno o dos elementos adicionales, encuentra la mediana de todos los elementos”, creo que puedes hacerlo en tiempo constante. (Una vez más, hay un montón de detalles para destacar, pero la idea básica es que agregar uno o dos elementos a una matriz no “aumenta mucho” la mediana).

Debería ser bastante directo aplicar la misma idea a 5 matrices.

Primero, convierta la pregunta a una más general. Encontrar el elemento Kth en N matrices ordenadas

  1. Encuentre (K / N) el elemento th en cada matriz ordenada con búsqueda binaria, digamos K1, K2 … KN

  2. Kmin = min (K1 … KN), Kmax = max (K1 … KN)

  3. Bote todos los elementos a menos de Kmin o más grandes que Kmax, digamos que X elementos se han desechado.

  4. Ahora repita el proceso mediante el elemento find (K – X) th en arreglos ordenados con los elementos restantes

No necesita hacer una fusión completa de las 5 matrices. Puedes hacer un tipo de fusión hasta que tengas (l + n + o + p + q) / 2 elementos, entonces tienes el valor mediano.