Dada la lista ayb, donde a tiene un elemento adicional en comparación con b, estoy tratando de ubicar ese elemento adicional que existe exclusivamente de una manera eficiente. Si bien esto se puede hacer fácilmente usando set (...

2
Robin 15 mar. 2021 a las 04:44

1 respuesta

La mejor respuesta

Puedes hacerlo en O(n log(n)) tiempo usando una clasificación. Después de ordenar, puede hacer un recorrido lineal para encontrar la primera diferencia. Los elementos duplicados complican la búsqueda binaria, que de otro modo sería posible.

def ldiff(a, b):
    a.sort()
    b.sort()
    for i, j in zip(a, b):
        if i != j:
            break
    else:
        i, j = a[-1], b[-1]
    return i if len(a) > len(b) else j 

Si se opone a la modificación in situ realizada por el método sort, utilice la función sorted en su lugar.

2
Mad Physicist 15 mar. 2021 a las 01:52