(Esta es una generalización de su idea de dos matrices.)
Si comienza 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 como esto: 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 segundo. El resultado sigue
Por lo tanto, 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, tirar los primeros elementos min (j, k) de una matriz y el último min (j, k) elementos de la matriz de b.
Itegre hasta que tenga 1 o 2 elementos en total.
Cada una de estas operaciones (es decir, encontrar la mediana de una matriz ordenada y tirar los elementos k desde el inicio o el final de una matriz) es un tiempo constante. Entonces cada iteración es tiempo constante.
Cada iteración arroja (más de) la mitad de los elementos de al menos una matriz, y usted solo puede hacer ese registro (n) veces para cada una de las cinco matrices ... Entonces el algoritmo general es log (n) .
[Actualización]
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 el número de elementos en la matriz (y las matrices están indexadas desde 0 y la división por 2 rondas).
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 prestado sugerencia de Himadri: Borra todos los elementos hasta e incluyendo una de su matriz, y todos los elementos abajo a e incluyendo b de su matriz, teniendo cuidado de eliminar el mismo número 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.
Iterate siempre que tengas 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 ay 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).
Por último, reducirá a unos pocos casos, el más delicado de los cuales es dos matrices restantes, uno de los 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 "empuja mucho" a la mediana).
¿Están cada uno individualmente ordenados, o cada conjunto también representa un rango dentro del cual no hay ningún valor de otro de los conjuntos? es decir, si uno tiene valores en el rango 1-5, ¿podría otro tener valores en el mismo rango? De lo contrario, solo necesita determinar el orden de las matrices (rango más bajo al más alto), sumar todas sus longitudes, dividir entre 2 para el elemento medio e ir a la matriz que tiene ese elemento. –
Gracias filip-fku. Dirigí tus preguntas. – codeObserver
Es un problema notorio porque la idea es relativamente fácil pero es extremadamente difícil de implementar correctamente. Para k> 2, la implementación empeora. Para mí, esta no es una buena para entrevistas tecnológicas. – galactica