arrays - ejemplo - que es un array en programacion
Mediana de 5 arreglos ordenados (3)
Estoy tratando de encontrar la solución para la mediana de 5 arreglos ordenados. Esta fue una entrevista de preguntas.
La solución que se me ocurrió fue combinar los 5 arreglos y luego encontrar la mediana [O (l + m + n + o + p)].
Sé que para 2 arreglos ordenados del mismo tamaño podemos hacerlo en log (2n). [comparando la mediana de ambos arreglos y luego tirando la mitad de cada arreglo y repitiendo el proceso]. .. Encontrar la mediana puede ser un tiempo constante en arreglos ordenados ... ¿entonces 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, como se pidió 5, ¿habría alguna solución para los arreglos ordenados de N?
Gracias por cualquier punteros.
Algunas aclaraciones / preguntas que le hice al entrevistador:
Son las matrices de igual longitud.
=> No
Supongo que habría una superposición en los valores de las matrices.
=> Si
Como ejercicio, creo que la lógica para 2 matrices no se extiende. Aquí hay un intento:
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
lanzar elementos [3,7,9] [4,8] [3,9] .. medianas 7,6,6
lanzar elementos [3,7] [8] [9] ..medians 5,8,9 ...
lanzar elementos [7] [8] [9] .. mediana = 8 ... ¿Esto no parece ser correcto?
La combinación de elementos ordenados => [2,3,4,7,8,9,15] => mediana esperada = 7
(Esta es una generalización de su idea para dos arreglos).
Si comienza observando 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 que una y menos de la mitad de sus elementos mayores que b. El resultado sigue.
Así que en la matriz que contiene a, tira los números menos que a; en la matriz que contiene b, descarte números mayores que b ... Pero solo tire la misma cantidad de elementos de ambas matrices.
Es decir, si a es j elementos desde el inicio de su matriz, y b es k elementos desde el final de su matriz, bota los primeros elementos min (j, k) de la matriz de a y el último min (j, k) ) elementos de la matriz de b.
Iterar hasta que haya bajado a 1 o 2 elementos en total.
Cada una de estas operaciones (es decir, encontrar la mediana de una matriz ordenada y eliminar 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 desecha (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 Himadri Choudhury señala en los comentarios, mi solución está incompleta; Hay un montón de detalles y casos de esquina para preocuparse. Entonces, para hacer las cosas un poco más ...
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 matrices) se indexan desde 0, y la división por 2 redondea hacia 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 varias matrices con la mediana inferior más pequeña y / o las matrices múltiples con la 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: 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. Así que está bien si este paso termina desechando elementos desde el principio y el final de la misma matriz.
Iterar mientras tengas tres o más arreglos. Pero una vez que haya reducido a uno o dos arreglos, debe cambiar su estrategia para ser exclusivo en lugar de inclusivo; solo borra hasta pero sin incluir a y hacia abajo pero sin incluir b. Continúe de esta manera siempre que los dos arreglos restantes tengan al menos tres elementos (lo que garantiza el progreso).
Finalmente, reducirá a unos pocos casos, el más complicado de los cuales son los dos arreglos restantes, uno de los cuales tiene uno o dos elementos. Ahora, si te preguntara: "Dada una matriz ordenada más uno o dos elementos adicionales, encuentra la mediana de todos los elementos", creo que puedes hacerlo en un tiempo constante. (Una vez más, hay un montón de detalles para armar, pero la idea básica es que agregar uno o dos elementos a una matriz no "empuja la mediana" mucho).
Debería ser bastante directo aplicar la misma idea a 5 arreglos.
Primero, convierta la pregunta a una más general. Encontrar el elemento Kth en N arreglos ordenados
Encuentre (K / N) el elemento th en cada matriz ordenada con búsqueda binaria, digamos K1, K2 ... KN
Kmin = min (K1 ... KN), Kmax = max (K1 ... KN)
Deseche todos los elementos menores que Kmin o mayores que Kmax, digamos que los elementos X se han desechado.
Ahora repita el proceso con el elemento encontrar (K - X) en las matrices ordenadas con los elementos restantes
No es necesario hacer una combinación completa de los 5 arreglos. Puedes hacer una ordenación de fusión hasta que tengas (l + n + o + p + q) / 2 elementos, entonces tienes el valor de la mediana.