2009-08-23 46 views
52

Tengo dos listas que necesito combinar donde la segunda lista tiene duplicados de la primera lista ignorados. .. Un poco difícil de explicar, así que déjame mostrar un ejemplo de cómo se ve el código, y lo que quiero como resultado.Combinación de dos listas y eliminación de duplicados, sin eliminar duplicados en la lista original

first_list = [1, 2, 2, 5] 

second_list = [2, 5, 7, 9] 

# The result of combining the two lists should result in this list: 
resulting_list = [1, 2, 2, 5, 7, 9] 

Se dará cuenta de que el resultado tiene la primera lista, incluyendo sus valores de dos "2", pero el hecho de que second_list también tiene un valor adicional 2 y 5 no se añade a la primera lista.

Normalmente, para algo como esto usaría conjuntos, pero un conjunto en first_list purgaría los valores duplicados que ya tiene. Así que simplemente me pregunto cuál es la mejor/más rápida forma de lograr esta combinación deseada.

Gracias.

+2

¿Están las listas siempre ordenadas? – Triptych

+1

¿Qué pasa si hay tres 2 en 'second_list'? – balpha

+0

@balpha: Sí, aún no he decidido completamente cómo quiero manejar eso. Es algo en lo que había pensado, pero lo dejé por mi indecisión al respecto :) –

Respuesta

95

Es necesario anexar a la primera lista de aquellos elementos de la segunda lista que no están en la primera - juegos son la forma más fácil de determinar cuáles son los elementos que son, como esto:

first_list = [1, 2, 2, 5] 
second_list = [2, 5, 7, 9] 

in_first = set(first_list) 
in_second = set(second_list) 

in_second_but_not_in_first = in_second - in_first 

result = first_list + list(in_second_but_not_in_first) 
print result # Prints [1, 2, 2, 5, 9, 7] 

O si prefiere una sola línea 8-)

print first_list + list(set(second_list) - set(first_list)) 
+2

O esto si lo necesita ordenado: imprime first_list + sorted (set (second_list) - set (first_list)) – hughdbrown

+0

List (set (first_list) | set (second_list)) # | se establece la intersección vea http://stackoverflow.com/questions/4674013/how-to-take-the-lists-y-combine-the-excluding-any-duplicates – staticd

+0

@staticd: Sí, pero eso da la respuesta incorrecta. Solo hay un '2' en tu resultado, cuando debería haber dos. – RichieHindle

3
resulting_list = first_list + [i for i in second_list if i not in first_list] 
+1

setify first_list y está "configurado" – u0b34a0f6ae

+0

La lista resultante no será ordenada. – avakar

+4

Es un algoritmo O (m * n). – hughdbrown

31
resulting_list = list(first_list) 
resulting_list.extend(x for x in second_list if x not in resulting_list) 
+1

También un algoritmo O (m * n). – hughdbrown

+3

¡Finalmente una respuesta que no involucra el lanzamiento en conjuntos! Prestigio. – SuperFamousGuy

+2

esto es, de hecho, O (n * m) pero puede ser útil cuando tiene una lista de cosas que no se pueden manejar y el rendimiento no es una preocupación – alcuadrado

1

Esto podría ayudar

def union(a,b): 
    for e in b: 
     if e not in a: 
      a.append(e) 

La función de unión fusiona la segunda lista en la primera, sin duplicar un elemento de a, si ya está en a. Similar a establecer el operador de la unión. Esta función no cambia b. Si a = [1,2,3] b = [2,3,4]. Después de la unión (a, b) hace que a = [1,2,3,4] y B = [2,3,4]

conjuntos
7

puede usar:

first_list = [1, 2, 2, 5] 
second_list = [2, 5, 7, 9] 

resultList= List(set(first_list)|set(second_list)) 
resultList=[1,2,5,7,9] 
+2

Ese es el resultado incorrecto. Lee la pregunta nuevamente – RichieHindle

0
first_list = [1, 2, 2, 5] 
    second_list = [2, 5, 7, 9] 

    newList=[] 
    for i in first_list: 
     newList.append(i) 
    for z in second_list: 
     if z not in newList: 
      newList.append(z) 
    newList.sort() 
    print newList 

[1 , 2, 2, 5, 7, 9]

1

puede también combinar las respuestas de RichieHindle y Ned Batchelder es para una average-case O (m + n) algoritmo que preserva el orden:

first_list = [1, 2, 2, 5] 
second_list = [2, 5, 7, 9] 

fs = set(first_list) 
resulting_list = first_list + [x for x in second_list if x not in fs] 

assert(resulting_list == [1, 2, 2, 5, 7, 9]) 

Tenga en cuenta que x in s has a worst-case complexity of O(m), por lo que el peor caso complejidad de este código sigue siendo O (m * n).

1
first_list = [1, 2, 2, 5] 
second_list = [2, 5, 7, 9] 

print(set(first_list + second_list)) 
Cuestiones relacionadas