Python并集与交集练习案例代码

题目描述

小鱼同学学习了并集和交集的概念。
（1）数组的并集：给定两个数组A，B ，把他们所有的元素合并在一起，并按照从小到大排序组成的集合，叫做数组A与数组B的并集；比如：数组{1,2,3}和{2,3,4}的并集是{1,2,3,4}。
（2）数的交集：给定两个数组 A，B，由所有属于数组 A 且属于数组B 的元素，并按照从小到大排序组成的集合，所组成的集合，叫做集合A与集合B的交集；比如：数组{1,2,3}和{2,3,4}的交集为{2,3}。
现给定2个数组，每个数组都含有若干不重复的元素，请分别求出两个数组的并集和交集（测试数据确认两个集合一定有交集）。

输入描述

第一行有两个整数m 和 n（m,n 都是10∼1000之间的整数），分别代表A,B 两个数组的长度。
第二行有m个整数，代表A数组存储的整数，用空格隔开。
第三行有n个整数，代表B数组存储的整数，用空格隔开。
注：两个集合的数都是大于等于0小于等于10000的整数。

输出描述

第一行输出两个数组的并集，用空格隔开这些元素。
第二行输出两个数组的交集，用空格隔开这些元素。

用例输入

3 4
2 1 3
5 4 3 2

用例输出

1 2 3 4 5
2 3

解题思路

1. 定义两个数组A、B，并读入数组长度和数组元素；
2. 分别对数组A、B进行排序；
3. 定义一个空集合union_set，用来存储两个数组的并集；
4. 定义一个空集合intersect_set，用来存储两个数组的交集；
5. 遍历数组A，判断数组B中是否存在该元素：
   • 如果存在，则将该元素加入intersect_set；
   • 如果不存在，则将该元素加入union_set；
6. 遍历数组B，判断数组A中是否存在该元素：
   • 如果不存在，则将该元素加入union_set；
7. 对union_set和intersect_set进行排序；
8. 输出union_set和intersect_set中的元素。

代码实现

m, n = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort()
union_set = set()
intersect_set = set()
for num in A:
    if num in B:
        intersect_set.add(num)
    else:
        union_set.add(num)
for num in B:
    if num not in A:
        union_set.add(num)
union_set = sorted(union_set)
intersect_set = sorted(intersect_set)
print(' '.join(map(str, union_set)))
print(' '.join(map(str, intersect_set)))

复杂度分析

• 时间复杂度为O(m+n)，其中m、n分别为数组A和B的长度；
• 空间复杂度为O(m+n)，用来存储union_set和intersect_set。