Es curioso, porque me hicieron exactamente la misma pregunta en una entrevista telefónica recientemente.
Lo resolví de la siguiente manera (suponiendo que desea la mediana sobre todos los valores): solo necesita avanzar más allá de la mitad de los valores más pequeños. Por lo tanto, puede mantener una lista de punteros al comienzo de cada matriz. Tenga el valor en la parte superior de estas matrices (junto con un puntero que le indica de qué matriz proceden) almacenadas en un contenedor, por ejemplo, un montón para que pueda recuperar fácilmente la más baja.
Ahora ejecute en un bucle: encuentre el número más bajo del montón. Elimine ese elemento y avance el puntero de la matriz correspondiente. Agregue el siguiente número de esa matriz al montón. Continúe esto n / 2 veces (donde n es el número total de elementos en todas las matrices). Si n es par, devuelve la media de los dos últimos elementos extraídos; de lo contrario, solo devuelve el último elemento extraído.
- ¿Qué es mejor en C #, mantener una variable con un tamaño de matriz o llamar a la longitud de la matriz?
- ¿Qué es el desaprendizaje en el algoritmo de aprendizaje automático?
- ¿El mismo algoritmo pertenece a algo, incluyendo política, mecánica cuántica, arte, deportes e ingeniería?
- En programación de computadoras, ¿por qué es importante la clasificación? ¿Cuándo se utilizan los algoritmos de clasificación en la codificación real?
- ¿Qué algoritmo usa la radio de Spotify para elegir las canciones?
Este algoritmo debe ser O (n log k), donde n es el número total de elementos yk es el número de matrices.
(en la entrevista, en realidad no pensé en el montón y lo almacené en una lista, lo que hizo que el algoritmo O (n * k). Me di cuenta de la idea del montón justo después de colgar: ‘()
