Algoritmos: apareo de listas ordenadas sin modificar las listas originarias

24/04/2018 | Autor: Eduardo Enriquez

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).


Tags