Mediana de 5 matrices ordenadas

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

Si se empieza por mirar las cinco medianas de los cinco arrays, 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 como esto: Si a es el mínimo de las medianas, y b es el máximo de las medianas, entonces cada matriz 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.

Así que en el array conteniendo a, deseche números menores que a; en el array conteniendo b, deseche números mayores que b... Pero solo deseche el mismo número de elementos de ambos arrays.

Es decir, si a es j elementos desde el inicio de su matriz, y b es k elementos desde el final de su matriz, se desechan los primeros elementos min(j,k) de la matriz de a y los últimos elementos min(j,k) de la matriz de b.

Itere hasta que haya bajado a 1 o 2 elementos en total.

Cada uno de estos las operaciones (es decir, encontrar la mediana de un array ordenado y desechar k elementos desde el principio o el final de un array) es tiempo constante. Así que cada iteración es tiempo constante.

Cada iteración arroja (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... Así que el algoritmo general es log (n).

[Actualizar]

Como señala Himadri Choudhury en los comentarios, mi solución está incompleta; hay muchos detalles y estuches de esquina de los que preocuparse. Por lo tanto, para dar cuerpo a las cosas un poco...

Para cada uno de los cinco arrays R, defina su "mediana inferior" como R[n/2-1] y su "mediana superior" como R[n/2], donde n es el número de elementos en el array (y los arrays se indexan a partir de 0, y la división por 2 rondas hacia abajo).

Sea "a" la más pequeña de las medianas inferiores, y "b" la más grande de las medianas superiores. Si hay varios arrays con la mediana más baja más pequeña y / o múltiples arrays con el mediana superior más grande, elija a y b de diferentes matrices (este es uno de esos casos de esquina).

Ahora, tomando prestada la sugerencia de Himadri: Borrar todos los elementos hasta e incluyendo a de su array, y todos los elementos hasta e incluyendo b de su array, teniendo cuidado de eliminar el mismo número de elementos de ambos arrays. 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 habríamos podido elegir uno de ellos de una matriz diferente. Por lo tanto, está bien si este paso termina desechando elementos desde el principio y el final de la misma matriz.

Itere siempre y cuando tenga tres o más matrices. Pero una vez que se ha reducido a solo uno o dos arrays, tiene que cambiar su estrategia para ser exclusivo en lugar de inclusivo; solo borra hasta pero sin incluir a y hasta pero sin incluir b. Continúe así siempre y cuando ambos de los arrays restantes tengan al menos tres elementos (que garantizan el progreso).

Finalmente, se reducirá a unos pocos casos, el más complicado de los cuales son dos arreglos restantes, uno de los cuales tiene uno o dos elementos. Ahora, si te pregunto: "Dado un arreglo ordenado 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 martillar, pero la idea básica es que agregar uno o dos elementos a una matriz no " empuja la mediana alrededor " mucho.)