Intercalación de Listas Ordenadas en Python

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

Resumen

¿Cómo se implementa la función MergeLists?

La implementación de la función MergeLists en Python ofrece un método eficiente para fusionar listas ordenadas. Este proceso es esencial en muchas aplicaciones de programación, donde mezclar y ordenar datos grandes se vuelve crítico. A continuación, se describe paso a paso cómo se desarrolla esta función para garantizar un rendimiento óptimo tanto en tiempo como en espacio.

def MergeLists(nums1, m, nums2, n):
    p1 = m - 1  # Última posición significativa en nums1
    p2 = n - 1  # Última posición en nums2
    p = m + n - 1  # Última posición total en nums1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] < nums2[p2]:
            nums1[p] = nums2[p2]
            p2 -= 1
        else:
            nums1[p] = nums1[p1]
            p1 -= 1
        p -= 1

    # Manejo del caso donde quedan elementos en nums2
    nums1[:p2 + 1] = nums2[:p2 + 1]

¿Cómo funcionan los apuntadores en esta función?

El uso de apuntadores es clave para el manejo eficiente de las listas dentro de MergeLists. Estos sirven para mantener un seguimiento de las posiciones actuales de los elementos en las listas que se están comparando y gestionando.

P1 y P2: Representan los índices de los elementos actuales de consideración en nums1 y nums2, respectivamente. Ambos apuntadores comienzan en las posiciones finales de sus listas.
P: Indica la posición en nums1 donde se colocará el siguiente elemento ordenado. Comienza en la última posición significativa de nums1.

Estos tres apuntadores se van ajustando a medida que se colocan los elementos comparados en las posiciones correspondientes, asegurando que los elementos más grandes se coloquen primero, dado que estamos trabajando de atrás hacia adelante.

¿Cuáles son los casos especiales que se deben considerar?

Al implementar esta función, es crucial prever casos excepcionales que podrían alterar el flujo del algoritmo si no se gestionan correctamente:

Diferentes longitudes de lista: Si nums1 y nums2 no tienen la misma longitud, las porciones no utilizadas pueden ser ignoradas o deben ser rellenadas. Si quedan elementos en nums2 sin usar, estos deben reemplazar las posiciones iniciales de nums1.

¿Cuál es la complejidad temporal y espacial de la función?

La eficiencia de esta función es una parte fundamental de su diseño:

Complejidad temporal: La función recorre cada elemento de nums1 y nums2 una sola vez. En consecuencia, la complejidad temporal es O(n + m), donde n y m son las longitudes de las dos listas.
Complejidad espacial: Solo utiliza variables adicionales para los apuntadores. No necesita espacio adicional proporcional al tamaño de las listas, por lo tanto, su complejidad espacial es constante, O(1).

Invitaría a los estudiantes y programadores a probar y personalizar este código para sus propios proyectos o ejercicios. Explorar y experimentar con diferentes casos de prueba no solo consolidará el entendimiento del algoritmo, sino que también enriquececerá su habilidad para resolver problemas complejos de programación. ¡Sigue avanzando y desarrollando tus habilidades en programación!

Nicolas Alpargatero

student•

Que calidad de solución de la profe 🐍 llegar un tiempo O(n) y espacio O(1).

Christopher Andrés Guano Valencia

student•

Comparto la solución en JavaScript / TypeScript

function merge_lists(
	nums1: number[], 
	m: number, 
	nums2: number[], 
	n: number
): number[] {
  let i = nums1.length - 1
  let p1 = m - 1
  let p2 = n - 1

  while (p1 >= 0 && p2 >= 0) {
    if (nums1[p1] >= nums2[p2]) {
      nums1[i] = nums1[p1]
      p1--
    } else {
      nums1[i] = nums2[p2]
      p2--
    }
    i--
  }

  for (i = 0; i < p2 + 1; i++) {
    nums1[i] = nums2[i]
  }

  return nums1
}

Ricardo Betancourt

student•

mi solución

def merge_lists(nums1, m, nums2, n):
   # Tu código aquí 👇
   z = m + n
   while m != 0 or n != 0:
      if m == 0:
         nums1[z-1] = nums2[n-1]
         n -= 1
      elif n == 0 or nums1[m-1] > nums2[n-1]:
         nums1[z-1] = nums1[m-1]
         m -= 1
      else:
         nums1[z-1] = nums2[n-1]
         n -= 1
      z -= 1
   return nums1

Andres Rodriguez

student•

Creo que tu solución falla para casos como:

nums1 = [3,3,7,0,0,0]

nums2 = [2,2,2]

Gerardo Gutierrez

student•

En python no es muy recomendable utilizar la expresión m != 0 porque los números negativos se consideran como True, además de que los índices negativos sí son validos en las listas. Por eso en python y para este caso es mas correcta la expresión m >= 0. 😉

Israel Cruz

student•

Mi solución en Python:

def merge_lists(nums1, m, nums2, n):
    p1 = m - 1
    p2 = n - 1
    p3 = m + n - 1
    while p3 >= 0: 
        if nums1[p1] > nums2[p2] and p1 >= 0 or p2 < 0:
            nums1[p3] = nums1[p1]
            p1 -= 1
        else:
            nums1[p3] = nums2[p2]
            p2 -= 1
        p3 -= 1
    return nums1

Andres Rodriguez

student•

Creo que tu solución falla para:

nums1 = [3,3,7,0,0,0]

nums2 = [2,2,2]

Irving Juárez

student•

Estaría bien que probara el código para verificar que funciona

Nicolas Alpargatero

student•

lo único que le falto fue ordenar las listas si nums2 es la que viene mayor que nums1:

if m > n:
        n, m = m, n
        nums1, nums2 = nums2, nums1

pero del resto, hasta mejor solución que una IA 🤓

Edwin Garcés Saucedo

student•

Esta fue la solución a la que llegué, pero claro, la de la clase es más corta y elegante, me la llevo para después:

def merge_lists(nums1, m, nums2, n):
   pointer1 = m - 1
   pointer2 = n - 1
   pointer3 = m + n - 1

   while pointer3 >= 0:
      should_compare = pointer2 >= 0 and pointer1 >= 0

      if should_compare and nums1[pointer1] < nums2[pointer2]:
         nums1[pointer3] = nums2[pointer2]
         pointer2 -= 1
         pointer3 -= 1
      elif should_compare and nums1[pointer1] > nums2[pointer2]:
         nums1[pointer3] = nums1[pointer1]
         pointer1 -= 1
         pointer3 -= 1
      elif pointer1 >= 0:
         nums1[pointer3] = nums1[pointer1]
         pointer1 -= 1
         pointer3 -= 1
      elif pointer2 >= 0:
         nums1[pointer3] = nums2[pointer2]
         pointer2 -= 1
         pointer3 -= 1
   return nums1

Alejandro Martinez

student•

Después de ver este video, creo que la condición final podría evitarse. En vista de que los números de la primera lista ya están ordenados, solo nos interesa asegurarnos que los de la segunda lista se incluyan y a no ser que esta sea más grande que la primera, el único índice que devemos verificar en el loop es el que está recorriendo la segunda lista. Sería de la siguiente forma:

Me corrigen si me equivoco en algo porfa...

def merge_lists(nums1, m, nums2, n):
    n1_idx = m - 1
    n2_idx = n - 1
    order_idx = len(nums1) -1

    while n2_idx >= 0:
        if n1_idx >= 0 and nums1[n1_idx] > nums2[n2_idx]:
            nums1[order_idx] = nums1[n1_idx]
            n1_idx -= 1
        else:
            nums1[order_idx] = nums2[n2_idx]
            n2_idx -= 1
        order_idx -= 1
                
    return nums1

Daniel Cueto

student•

Mi solucion en C++ #include <iostream>#include <vector> using namespace std; vector<int> MergeTwoSortedList(vector<int> nums1, int m, vector<int> nums2, int n) { vector<int> res; int i = 0; int j = 0; while (i < m && j < n) { if (nums1[i] < nums2[j]) { res.push_back(nums1[i]); i++; } else if (nums1[i] == nums2[j]) { res.push_back(nums1[i]); res.push_back(nums2[j]); i++; j++; } else { res.push_back(nums2[j]); j++; } } while (i < m) { res.push_back(nums1[i]); i++; } while (j < n) { res.push_back(nums2[j]); j++; } return res;} int main() { int m; int n; cin >> m; cin >> n; vector<int> nums1(m+n, 0); vector<int> nums2(n, 0); //Los datos vendran desde la entrada for (int i = 0; i < m+n; i++) { cin >> nums1[i]; } for (int i = 0; i < n; i++) { cin >> nums2[i]; } //Mostrar el vector resultante vector<int> res = MergeTwoSortedList(nums1, m, nums2, n); for (int i = 0; i < res.size(); i++) { cout << res[i] << endl; }}

#include <iostream>
#include <vector>

using namespace std;

vector<int> MergeTwoSortedList(vector<int> nums1, int m, vector<int> nums2, int n) {
    vector<int> res;
    int i = 0;
    int j = 0;
    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) {
            res.push_back(nums1[i]);
            i++;
        } else if (nums1[i] == nums2[j]) {
            res.push_back(nums1[i]);
            res.push_back(nums2[j]);
            i++; j++;
        } else {
            res.push_back(nums2[j]);
            j++;
        }
    }
    while (i < m) {
        res.push_back(nums1[i]);
        i++;
    }
    while (j < n) {
        res.push_back(nums2[j]);
        j++;
    }
    return res;
}

int main() {
    int m;
    int n;
    cin >> m;
    cin >> n;
    vector<int> nums1(m+n, 0);
    vector<int> nums2(n, 0);
    //Los datos vendran desde la entrada
    for (int i = 0; i < m+n; i++) {
        cin >> nums1[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> nums2[i];
    }
    //Mostrar el vector resultante
    vector<int> res = MergeTwoSortedList(nums1, m, nums2, n);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << endl;
    }
}

David Higuera

student•

def merge_lists(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1

    while k > -1:
        if i >= 0 and (j < 0 or nums1[i] > nums2[j]):
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    return nums1

David Higuera

student•

def merge_lists(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1

    while k > -1:
        if i >= 0 and (j < 0 or nums1[i] > nums2[j]):
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    return nums1
```def merge\_lists(*nums1*, *m*, *nums2*, *n*):    i = *m* - 1    j = *n* - 1    k = *m* + *n* - 1
    while k > -1:        if i >= 0 and (j < 0 or *nums1*\[i] > *nums2*\[j]):            *nums1*\[k] = *nums1*\[i]            i -= 1        else:            *nums1*\[k] = *nums2*\[j]            j -= 1        k -= 1    return *nums1*

Leonardo Bazán Márquez

student•

def merge_lists(nums1, m, nums2, n):
   if n+m < len(nums1):
      return print("Error, invalid size")
   i = m + n - 1
   j = m - 1
   k = n - 1

   while j >= 0 and k >= 0:   
      if nums1[j] > nums2[k] :
         nums1[i] = nums1[j]
         j-=1
      else:
         nums1[i] = nums2[k]
         k-=1
      i-=1
   while j >= 0:
      nums1[i] = nums1[j]
      j-=1
      i-=1
   while k >= 0:
      nums1[i] = nums2[k]
      k-=1
      i-=1
   return nums1
```Así lo hice

Miguel Angel Reyes Moreno

student•

Este problema se puede arreglar en 3 líneas de código 😅

def merge\_two\_sorted\_lists(nums1, nums2):
&#x9;nums1 = \[n for n in nums1 if n != 0]
&#x9;return sorted(nums1+nums2)

Noldia Chavez Cavero

student•

En java:

public int[] merge(int[] nums1, int[] nums2, int m, int n) {  
  
	for (int i = m + n - 1 ; i > 0 ; i--) {  
		if ( m < 1 || n < 1) break;  
		if ( nums1[m-1] >= nums2[n-1] ) {  
			nums1[i] = nums1[m-1];  
			m--;  
		} else {  
			nums1[i] = nums2[n-1];  
			n--;  
		}  
	}  
	  
	if (m != n)  
		System.arraycopy(nums2, 0, nums1, 0, n);  
	  
	return nums1;  
}
```public int\[] merge(int\[] nums1, int\[] nums2, int m, int n) { &#x20;

&#x20;&#x20;

&#x9;for (int i = m + n - 1 ; i > 0 ; i--) { &#x20;

&#x9;	if ( m < 1 || n < 1) break; &#x20;

&#x9;	if ( nums1\[m-1] >= nums2\[n-1] ) { &#x20;

&#x9;		nums1\[i] = nums1\[m-1]; &#x20;

&#x9;		m--; &#x20;

&#x9;	} else { &#x20;

&#x9;		nums1\[i] = nums2\[n-1]; &#x20;

&#x9;		n--; &#x20;

&#x9;	} &#x20;

&#x9;} &#x20;

&#x9; &#x20;

&#x9;if (m != n) &#x20;

&#x9;	System.arraycopy(nums2, 0, nums1, 0, n); &#x20;

&#x9; &#x20;

&#x9;return nums1; &#x20;

}

Arley Santiago

student•

def merge_lists(nums1: list, m: int, nums2: list, n: int) -> list:
    X = [0 for _ in range(m + n)]

    if m == 0 or n == 0:
        return m + n
    i = 0
    j = 0
    k = 0
    while i < m and j < n:
        if nums1[i] < nums2[j]:
            X[k] = nums1[i]
            i += 1
        else:
            X[k] = nums2[j]
            j += 1
        k += 1

    if i < m:
        X[k:] = nums1[i:]

    if j < n:
        X[k:] = nums2[j:]
    return X

Santiago Amaya

student•

def two_merge(a,b):
    pi, pf = len(a)//2-1, len(a)-1
    pb = len(b)-1
    while pf >= 0:
        if pi >= 0 and a[pi] > b[pb]:
            a[pf] = a[pi]
            pf -= 1
            pi -= 1
        else:
            a[pf] = b[pb]
            pf -= 1 
            pb -= 1 

    return a

a=[1,2,3,0,0,0,0]
b=[-4,5,6,7]
print(two_merge(a,b))
```no se para que tipo de caoss funcione pero para el de la clase funciona bien&#x20;

Santiago Amaya

student•

def two_merge(a,b):
    pi, pf = len(a)//2-1, len(a)-1
    pb = len(b)-1
    while pf >= 0:
        if pi >= 0 and a[pi] > b[pb]:
            a[pf] = a[pi]
            pf -= 1
            pi -= 1
        else:
            a[pf] = b[pb]
            pf -= 1 
            pb -= 1 

    return a

a=[1,2,3,0,0,0,0]
b=[-4,5,6,7]
print(two_merge(a,b))
```def two\_merge(a,b):    pi, pf = len(a)//2-1, len(a)-1    pb = len(b)-1    while pf >= 0:        if pi >= 0 and a\[pi] > b\[pb]:            a\[pf] = a\[pi]            pf -= 1            pi -= 1        else:            a\[pf] = b\[pb]            pf -= 1             pb -= 1&#x20;
    return a
a=\[1,2,3,0,0,0,0]b=\[-4,5,6,7]print(two\_merge(a,b))

Santiago Amaya

student•

def two_merge(a,b):
    pi, pf = len(a)//2-1, len(a)-1
    pb = len(b)-1
    while pf >= 0:
        if pi >= 0 and a[pi] > b[pb]:
            a[pf] = a[pi]
            pf -= 1
            pi -= 1
        else:
            a[pf] = b[pb]
            pf -= 1 
            pb -= 1 

    return a

a=[1,2,3,0,0,0,0]
b=[-4,5,6,7]
print(two_merge(a,b))
```def two\_merge(a,b):    pi, pf = len(a)//2-1, len(a)-1    pb = len(b)-1    while pf >= 0:        if pi >= 0 and a\[pi] > b\[pb]:            a\[pf] = a\[pi]            pf -= 1            pi -= 1        else:            a\[pf] = b\[pb]            pf -= 1             pb -= 1&#x20;
    return a
a=\[1,2,3,0,0,0,0]b=\[-4,5,6,7]print(two\_merge(a,b))

Santiago Amaya

student•

(def two_merge(a,b): pi, pf = len(a)//2-1, len(a)-1 pb = len(b)-1 while pf >= 0: if pi >= 0 and a[pi] > b[pb]: a[pf] = a[pi] pf -= 1 pi -= 1 else: a[pf] = b[pb] pf -= 1 pb -= 1 return a a=[1,2,3,0,0,0,0]b=[-4,5,6,7]print(two_merge(a,b)))

Santiago Amaya

student•

def two_merge(a,b): pi, pf = len(a)//2-1, len(a)-1 pb = len(b)-1 while pf >= 0: if pi >= 0 and a[pi] > b[pb]: a[pf] = a[pi] pf -= 1 pi -= 1 else: a[pf] = b[pb] pf -= 1 pb -= 1 return a a=[1,2,3,0,0,0,0]b=[-4,5,6,7]print(two_merge(a,b))

Deivison Jiménez

student•

esta es mi solución

using System;
using System.Linq;
using System.Reflection.Metadata.Ecma335;
using System.Xml.Schema;



int[] nums1 = { 1, 2, 3, 0, 0, 0 };
int[] nums2 = { 2, 5, 6 };
int m = 3;
int n = 3;
int t = m + n;
int[] nums3 = new int[t];
Compara(nums1, nums2, m, n);

void Compara(int[] nums1, int[] nums2, int m, int n)
{

    List<int> result = new List<int>();
    
    foreach (var item in nums1)
    {
        if (item != 0)
        {
            Console.WriteLine("arreglo1 " + item);

            result.Add(item);
            
             nums3 = result.ToArray();


        }
    }

    Console.WriteLine("------------------------------------------------");

    foreach (var item in nums2)
    {

        Console.WriteLine("arreglo2 " + item);
        result.Add(item);
        nums3 = result.ToArray();

    }

    Console.WriteLine("------------------------------------------------");
    foreach (var item1 in nums3.OrderBy(n=> n))
    {
        
        Console.WriteLine("arreglo3 " + item1);
    }

}
```using System;

using System.Linq;

using System.Reflection.Metadata.Ecma335;

using System.Xml.Schema;







int\[] nums1 = { 1, 2, 3, 0, 0, 0 };

int\[] nums2 = { 2, 5, 6 };

int m = 3;

int n = 3;

int t = m + n;

int\[] nums3 = new int\[t];

Compara(nums1, nums2, m, n);



void Compara(int\[] nums1, int\[] nums2, int m, int n)

{



&#x20;   List\<int> result = new List\<int>();

&#x20;  &#x20;

&#x20;   foreach (var item in nums1)

&#x20;   {

&#x20;       if (item != 0)

&#x20;       {

&#x20;           Console.WriteLine("arreglo1 " + item);



&#x20;           result.Add(item);

&#x20;          &#x20;

&#x20;            nums3 = result.ToArray();





&#x20;       }

&#x20;   }



&#x20;   Console.WriteLine("------------------------------------------------");



&#x20;   foreach (var item in nums2)

&#x20;   {



&#x20;       Console.WriteLine("arreglo2 " + item);

&#x20;       result.Add(item);

&#x20;       nums3 = result.ToArray();



&#x20;   }



&#x20;   Console.WriteLine("------------------------------------------------");

&#x20;   foreach (var item1 in nums3.OrderBy(n=> n))

&#x20;   {

&#x20;      &#x20;

&#x20;       Console.WriteLine("arreglo3 " + item1);

&#x20;   }



}