algorithm - examples - fusionando matrices ordenadas

algorithms book

Question

Posibles duplicados:
Fusionando dos listas ordenadas
Algoritmo para la fusión N-way

Dados k arreglos ordenados, cada uno de longitud n, construyen un solo array combinado y ordenado. Enfóquese en el tiempo de ejecución y la complejidad del espacio.

Fuente: entrevista entrevista de Amazon.
¿Alguna idea? Gracias

Answer 1

Haz un montón desde el primer elemento en cada matriz. Extraiga el elemento head del montón, insértelo en la matriz de resultados y luego tome el siguiente elemento del array del que proviene el montón e insértelo en el montón. Repita hasta que consuma todas las matrices.