J'essaie de trouver l'intersection et l'union de deux listes pour une affectation, cependant, je ne peux pas utiliser d'ensembles . D'après la théorie des ensembles, une intersection entre deux ensembles correspond aux éléments qui se trouvent dans les deux ensembles. Une union est tous les éléments des deux ensembles, sans répétition. Jusqu'à présent, j'ai:

setA = [1,2,3,4,5,6,7,8,9]
setB = [1,5,0,9]

def getUnion(a, b):
    return a + b

def getIntersection(a, b):
    return 

Ma fonction d'union renvoie des doublons. Existe-t-il un moyen de simplement trouver le syndicat?

De plus, quelle est la meilleure approche pour trouver l'intersection?

0
user9603529 12 avril 2018 à 08:12

4 réponses

Meilleure réponse

Vous pouvez utiliser collections.Counter à la place pour calculer l'union et intersection

>>> from collections import Counter

>>> c = Counter(setA + setB)
>>> [a[0] for a in c.items() if a[1] > 1] #Intersection
>>> [1,5,9]

>>> list(c.keys()) #Union
>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

L'objet Counter contient les données au format:

>>> c
>>> Counter({1: 2, 5: 2, 9: 2, 0: 1, 2: 1, 3: 1, 4: 1, 6: 1, 7: 1, 8: 1})

La clé est les éléments de la liste et la valeur est l'occurrence de l'élément dans la liste.

0
Sohaib Farooqi 12 avril 2018 à 05:35

Supposons donc que vous pouvez utiliser sort. Triez d'abord deux listes, puis faites avec deux pointeurs, déplacez un pointeur avec une valeur plus petite vers l'avant à chaque fois.

Pour l'union func, ajoutez toutes les valeurs à chaque fois et avancez les deux pointeurs lorsque leurs valeurs sont égales. Pour les fonctions d'intersection, ajoutez uniquement des valeurs lorsque les valeurs sont égales.

Temps O (nlogn + n) -> O (nlogn)

0
TianChen Wang 12 avril 2018 à 05:26

Union et intersection sans utiliser d'ensembles:

setA = [1,2,3,4,5,6,7,8,9]
setB = [1,5,0,9]

intersection = [i for i in setA if i in setB]
list_union = list({i: i for i in setA + setB}.values())

print(intersection)
print(list_union)

Production:

[1, 5, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

Explication :

Pour l'union:

[i for i in setA if i in setB]

Parcourez simplement setA et ajoutez des éléments qui se trouvent également dans setB

Pour l'intersection:

list({i: i for i in setA + setB}.values())

Crée un dictionnaire où les clés et les valeurs sont le résultat de setA + setB. Étant donné que les clés d'un dictionnaire sont uniques, les doublons n'apparaissent pas dans le dictionnaire final et list(dct.values()) est utilisé pour extraire uniquement les valeurs nécessaires du dictionnaire.

0
user3483203 12 avril 2018 à 05:45

Essaye ça:

setA = [1,2,3,4,5,6,7,8,9]
setB = [1,5,0,9]

print (list(set(setA).intersection(setB)))

Production:

[1, 5, 9]
[Finished in 0.0s]
-1
rahul mehra 12 avril 2018 à 05:17