| Author: Eduardo Enriquez

Algoritmos: apareo de listas ordenadas sin modificar las listas originarias

Un problema t铆pico de entrevista es ordenar dos listas con elementos ya ordenados previamente. La idea es tener en cuenta que ya estan ordenados y no reordenar (que ser铆a el peor camino). Para esto voy adicionando los elementos m谩s peque帽os y luego extender si quedo un subconjunto por fuera del "comparado" en las iteraciones del while. Bueno aqu铆 va el algoritmo.

def merge_sorted_arrays(a, b):
    len_a = len(a)
    len_b = len(b)

    pos_a = 0
    pos_b = 0

    merged_list = []
    while pos_a < len_a and pos_b < len_b:
        if a[pos_a] <= b[pos_b]:
            merged_list.append(a[pos_a])
            pos_a += 1
        else:
            merged_list.append(b[pos_b])
            pos_b += 1

    if pos_a < len_a:
        merged_list.extend(a[pos_a:])
    if pos_b < len_b:
        merged_list.extend(b[pos_b:])

    return merged_list

a = [1, 2, 3, 4]
b = [3, 3, 8, 9]
expected = [1, 2, 3, 3, 3, 4, 8, 9]


result = merge_sorted_arrays(a, b)
print(expected == result)

No es gran cosa, simplemente uso una 3ra lista para ir guardando los elementos. Y luego extenderal segun la lista que se haya quedado sin recorrer o sea con los elementos de numeros m谩s grandes (y ordenados).

Related Posts