如何找到列表的交集和并集（不使用集合）

Question

我试图为一个作业找到两个列表的交集和并集，但是，我不能使用集合。根据集合论，两个集合之间的交集是两个集合中的元素。联合是两个集合中的所有元素，没有重复。到目前为止我有：

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

我的联合函数返回重复项。有没有办法简单的找到union？

此外，找到交点的最佳方法是什么？

Answer 1

试试这个：

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

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

输出：

[1, 5, 9]
[Finished in 0.0s]

Answer 2

不使用集合的并集和交集：

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)

输出：

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

解释:

联合：

[i for i in setA if i in setB]

简单地遍历 setA 并添加也在 setB

中找到的元素

交叉路口：

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

创建一个字典，其中的键和值是 setA + setB 的结果。由于字典中的键是唯一的，重复项不会出现在最终字典中，并且 list(dct.values()) 用于仅从字典中提取所需的值。

Answer 3

因此，假设您可以使用 sort。先对两个列表进行排序，然后对两个指针进行排序，每次向前移动一个值较小的指针。

对于联合函数，每次将所有值相加，当它们的值相等时，将两个指针向前移动。对于intersection func，只有当值相等时才添加值。

时间 O(nlogn+n)->O(nlogn)

Answer 4

您可以使用 collections.Counter 来计算并集和交集

>>> 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]

Counter 对象以以下格式保存数据：

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

键是列表中的元素，值是元素在列表中的出现。

如何找到列表的交集和并集（不使用集合）

How to find Intersection and Union of a List (without using sets)

python

union

intersection