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

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 

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

还有，找到十字路口的最佳方法是什么？在

Answer 1

可以改为使用^{}来计算并集和交集

>>> 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对象以格式保存数据：

^{pr2}$

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

Answer 2

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

对于union func，每次将所有值相加，并在两个指针的值相等时向前移动两个指针。 对于“交集函数”，仅在值相等时添加值。在

时间O（nlogn+n）—>；O（nlogn）

Answer 3

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

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)

输出：

^{pr2}$

说明：

对于联合体：

[i for i in setA if i in setB]

只需循环setA并添加在setB中也可以找到的元素

对于交叉口：

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

创建一个字典，其中的键和值是setA + setB的结果。{cd4>在字典中是唯一的，因为字典中的键是唯一的。在