Combine dos secuencias ordenadas
Recorra ambas listas con un puntero en cada una
Combine dos secuencias ordenadas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El paso de fusión
Dadas dos listas ordenadas, combínelas en una sola lista ordenada. Esta fusión es el núcleo de merge sort y aparece en muchos lugares. 🔗
Dos entradas, un puntero en cada una
Asigne a cada lista su propio puntero, ambos comenzando en el índice 0. Los recorrerá hacia delante simultáneamente, nunca hacia atrás.
i = 0
j = 0Elija siempre el menor
En cada paso, compare los dos primeros elementos. Añada el menor al resultado, porque debe ser el siguiente en el orden ordenado.
Avance el puntero ganador
Después de tomar un valor, avance únicamente el puntero del que procedía. La otra lista aún conserva su elemento más pequeño a la espera.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1El bucle principal
Siga fusionando mientras ambas listas aún tengan elementos. Cuando una se quede sin elementos, la comparación deja de tener sentido.
while i < len(a) and j < len(b):
# compare and append
passAgote los elementos restantes
Cuando una lista se vacía, la otra ya está ordenada, así que solo tiene que append directamente al resultado los elementos restantes de su parte final.
out.extend(a[i:])
out.extend(b[j:])Por qué las partes finales no cuestan nada
La parte final restante ya está ordenada, por lo que no hace falta comparar más. Una de esas dos llamadas a extend simplemente no añade nada.
Tiempo lineal en total
Cada elemento se examina una vez, así que fusionar dos listas de tamaños n y m cuesta O(n + m) de tiempo. Es lo más rápido posible.
Mantenga la estabilidad
Usar <= cuando los valores son iguales conserva los elementos equivalentes en su orden original. Esa estabilidad importa cuando se transportan datos adicionales.
También puede fusionar al revés
Para fusionar en un búfer sin espacio libre, recorra desde el final y coloque el elemento más grande en último lugar. Es la misma idea, reflejada.
De merge a merge sort
Dividir, ordenar las mitades y luego fusionarlas: esa recursión es merge sort. La fusión con dos punteros que acaba de aprender es su motor principal.
Comprobación rápida
Está fusionando dos listas ordenadas con un puntero en cada una.
Repaso
Recorra dos listas ordenadas con un puntero en cada una, eligiendo siempre el primer elemento menor, y después agote la parte final. Se ejecuta en O(n + m) y es la base de merge sort. 🚀
Preguntas frecuentes
¿La lección «Combine dos secuencias ordenadas» es gratis?
Sí — el texto completo de «Combine dos secuencias ordenadas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Combine dos secuencias ordenadas»?
Recorra ambas listas con un puntero en cada una Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Combine dos secuencias ordenadas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Dos punteros en un array ordenado
- Encuentre un par con una suma dada
- Elimine duplicados en el propio array
- Combine dos secuencias ordenadas