Combinar Listas Ordenadas en un Array Ascendente

Clase 8 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿Cómo combinar dos listas ordenadas?

En este enfoque abordaremos el problema de combinar dos listas de enteros, nums1 y nums2, cada una ordenada en orden ascendente. Nuestro objetivo será fusionar estas listas en un único array también ordenado de manera ascendente. Vamos a analizar las entradas necesarias, el proceso de fusión, y algunas recomendaciones para resolver este problema de manera eficiente.

¿Cuáles son las entradas necesarias?

Para resolver este problema, debemos entender las entradas que corren dentro de nuestro algoritmo:

nums1: Una lista de enteros preordenada en orden ascendente.
nums2: Otra lista de enteros también preordenada en orden ascendente.
m: Cantidad de elementos reales en nums1.
n: Cantidad de elementos reales en nums2.

¿Cómo es el proceso de fusión?

El proceso de combinación no solo consiste en unir las listas, sino hacerlo manteniendo el orden ascendente:

Tamaño final de nums1: La lista nums1 tiene una longitud de m + n, donde los primeros m elementos son los números reales y los últimos n elementos son ceros. Estos ceros deben ser ignorados para efectos del problema.
Fusión de listas: Combinar nums1 y nums2 implica mover los elementos efectivos juntos en orden ascendente.

# Ejemplo de cómo se podrían combinar las listas:

# Ejemplo de entrada:
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3

# Nuestras listas se ven así:
# nums1: [1, 2, 3, 0, 0, 0]
# nums2: [2, 5, 6]

# Después de la fusión, deberíamos obtener:
# nums1 = [1, 2, 2, 3, 5, 6]

¿Qué buenas prácticas se recomiendan seguir?

Diagramar antes de implementar: Antes de lanzarse a codificar, es útil diagramar la solución y planificar los pasos que se seguirán.
Analizar complejidad espacial y temporal: Reflexionar sobre la eficiencia del algoritmo en términos de espacio y tiempo es crucial, especialmente para casos con grandes conjuntos de datos.
Discutir y comentar: Compartir tu solución y complejidades logradas puede ayudar a mejorar tanto tu comprensión como la de otros.

¿Por qué es importante practicar problemas como este?

Resolver problemas de algoritmo como "Merge Two Sorted Lists" es una excelente manera de mejorar habilidades de programación, especialmente en temas como manipulación de arrays y listas, además de establecer bases sólidas para entender algoritmos de ordenamiento más complejos. Practicar estos desafíos mejora la eficiencia y el pensamiento crítico al encarar problemas complejos en programación.

Anímate a intentar esta solución y sigue practicando para fortalecer tus habilidades en programación, ¡la práctica constante es la clave del éxito!

Victor Hugo Vázquez Gómez

student•

Al principio no le entendia porque dice que m tiene la longitud de nums1 y luego sale con que nums1 tiene la longitud de m + n 💀

Ya viendo el ejemplo le entendi xD

Miguel Angel Reyes Moreno

student•

Un pequeño error de lógica, quizás xD

Nicolas Alpargatero

student•

Overview

Dadas dos listas de números enteros nums1 y nums2, cada una ordenada en orden ascendente, y dos enteros m y n, que representan la cantidad de elementos en nums1 y nums2 respectivamente. . Combinar nums1 y nums2 en un único array ordenado de forma ascendente. . Para ello, nums1 tienen una longitud de m+n, donde los primeros m elementos denotan los elementos que deben ser combinados, y los últimos n elementos son 0 y deben ser ignorados. .

si en una lista hay 3 elementos y en la otra 4, entonces nums1 tiene 7

Ejemplo

nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3

---> [1, 2, 2, 3, 5, 6]

Juan Pablo Reina Gutierrez

student•

La complejidad temporal es de O(n) ya que hay un único bucle que hace el recorrido de las listas a combinar teniendo en cuenta 3 variables (donde una sirve para recorrer nums1, otra para recorrer nums2 y otra auxiliar para guardar el elemento de la iteración anterior) que sirven para reorganizar los elementos en la nueva lista.

La complejidad espacial también es O(n) debido a que si la cantidad de datos aumenta, siempre se va a generar un array con el doble de tamaño que "nums2" y además las variables temporales de recorrido siempre van a tener el mismo tamaño reservado en memoria.

Carlos Axel Rodriguez Berrelleza

student•

Les dejo el problema en LeetCode: https://leetcode.com/problems/merge-sorted-array/

José López Lara

student•

Comparto mi solución, segun yo tiene una complejidad espacial de O(n) y una temporar de O(m), desconosco si O(m) se termine considerando O(n)

def combineTwoOrderedList(nums1, nums2, m, n) -> list:
  # Initialize my pointers
  nums1Pointer = m - 1
  nums2Pointer = n - 1
  orderedPointer = m + n - 1
  
  # Defining cycle for ordering
  while nums2Pointer >= 0:

    if nums2[nums2Pointer] >= nums1[nums1Pointer]:
      nums1[orderedPointer] = nums2[nums2Pointer]
      nums2Pointer -= 1 
    else: 
      nums1[orderedPointer] = nums1[nums1Pointer]
      nums1Pointer -= 1
    orderedPointer -= 1 

  return nums1

# Params Given
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
m = 3
n = 3

sortedList = combineTwoOrderedList(nums1, nums2, m, n)

for elemnet in sortedList:
  print(elemnet)

Karla Angelica Doctor Mauricio

student•

def sort_numbers(nums1, nums2):
  idx_1 = idx_2 = 0; ans = []
  while idx_1<len(nums1) and idx_2<len(nums2):
    if nums1[idx_1] < nums2[idx_2]:
      ans.append(nums1[idx_1])
      idx_1+=1
    else:
      ans.append(nums2[idx_2])
      idx_2+=1

  while idx_1<len(nums1):
    ans.append(nums1[idx_1])
    idx_1+=1

  while idx_2<len(nums2):
    ans.append(nums2[idx_2])
    idx_2+=1
  return ans
#Temporal O(n)
#Espacial O(n)

nums1 = [3,7,9,0,0,0]
nums2 = [5,6,7]
num1 = 6
num2 = 3

nums1 = nums1[:num2]
sort_numbers(nums1, nums2)

Miguel Angel Reyes Moreno

student•

Propongo mi solución antes de ver el siguiente vídeo, en TypeScript:

const mergeTwoSortedLists = (nums1: number[], nums2: number[]): number[] => { nums1 = nums1.filter(n => n !== 0) return (nums1.concat(nums2)).sort((nums1, nums2) => nums1 - nums2)}

Marcos Mesias

student•

Nose si lo hice bien o mal, no se debe a que mi codigo este mal, sino a que entendiera mal el problema, pero al final mi código da el resultado esperado.

Las variables n y m son innecesarias ya que sumas son la longitud de nums1, osea n+m es igual a len(nums1), pero igual puse esas variables en mi código como forma representativa.

Kengya Moncada

student•

Joan paredes yupanqui

student•

Carlos Raúl Romero Martínez

student•

La complejidad es de n+m al ya estar ordenadas, creo saber hacia donde va esto, esto es el principio para algoritmos como el mergue sort

Combinar Listas Ordenadas en un Array Ascendente

Introducción

Patrones de Arreglos y Strings: Ventana Deslizante y Dos Apuntadores

Arrays y Strings: Funcionamiento y Complejidades Temporales

Dos Apuntadores

Patrón de Dos Apuntadores en Algoritmos de Lista

Verificación de Orden en Diccionario Alienígena

Ordenamiento de Palabras en Idiomas Alienígenas

Playground: Verifying Alien Dictionary

Ordenación de Palabras en Diccionario Alienígena