Python ⼊门习题（80）——OpenJudge 百练习题：集合运算
big apple
OpenJudge 百练第4088号习题：集合运算
题⽬描述
来源
——
要求
总时间限制: 3000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB
描述
设 A = {a1, a2, … , an}, B = {b1, b2, … , bm} 是⾮负整数集合，其中m = O(logn)。
设计算法计算集合 C = (A − B) ∪ (B − A)。
输⼊
输⼊⽂件包含2⾏。
第1⾏的第⼀个数为n，表⽰A集合的⼤⼩，接下来跟有A集合中的包含的n个⾮负整数。
第2⾏的第⼀个数为m，表⽰B集合的⼤⼩，接下来跟有B集合中的包含的m个⾮负整数。
两个集合中的数按照从⼩到⼤的顺序给出，n <= 10输出
输出⽂件包含1⾏，表⽰计算出的C集合中所包含的整数。
请将这些整数按照从⼩到⼤的顺序排序。
horn样例输⼊
8 1 3 5 6 8 10 12 30
3 1 3 7
样例输出
5 6 7 8 10 12 30
解题思路
1. 采⽤以下做法，在OpenJudge提交代码后，得到的结论是超时。⽤input().split()读⼊第⼀⾏数据，接着把n个整数存为集合A（即t 类型）。同样步骤得到集合B。再求出A-B, B-A，然后求出C = (A − B) ∪ (B − A)。最后，把C集合转换为列表，排序，输出。
2. 要注意到，两个集合中的数按照从⼩到⼤的顺序给出。⽽且，m = O(logn)，这⾥n是集合A的元素个数，m是集合B的元素个数。
海边的卡夫卡语录3. 于是，修改计算C = (A − B) ∪ (B − A)的步骤。核⼼思路改为C = A ∪ B - A B 。具体步骤是：对于列表B（list类型，⾮集合类型）中的每⼀个元素b，⽤⼆分查找法在集合A（list类型，⾮集合类型）中找出第⼀个⼤于等于b的元素t，如果b等于t，那么从集合A 中去除b，否则把b插⼊到t之前（这样保证有序性）。
4. 采⽤第3点的做法后，在OpenJudge提交代码后，得到的结论是内存超出额度。
5. ⽤array类型（⽐list节省内存）来存储A和B，依旧发⽣内存超出额度。后来，认识到input().split()会⽣成字符串列表，10个字符串对象会占⽤巨额内存。因此，不能使⽤input().split() 。
6. 解决第5点所说的问题的对策是，⽤input()读⼊⼀⾏，存⼊line变量，然后从左到右逐个字符地扫描，
抽取出整数存⼊array数组中。
7. 基于第3点和第6点，在OpenJudge提交代码后，成功通过。
参考答案
6
∩6
#import time
import bict
import array
#读⼊⼀⾏整数，存⼊array 数组中
def read_nums ():
nums = array .array ('L')
line = input ()
num = ''
for s in line :
if s != ' ':
num += s
elif len (num ) > 0:
nums .append (int (num )) #把数字加⼊nums 序列中
num = ' '
if len (num ) > 0:
nums .append (int (num )) #不要忘记尾部的数字
return nums规格英文
# t0 = time.process_time()
A = read_nums ()
B = read_nums ()
addictiveA .pop (0)
kler
B .pop (0)幼儿英语
# t1 = time.process_time()
# print("输⼊累计时间：", t1 - t0)swansong
for b in B :
i = bict .bict_left (A , b ) #⼆分查找，找集合A 中第⼀个⼤于等于b 的元素的索引
if i != len (A ) and A [i ] == b :
A .pop (i ) #在集合A 中找到等于b 的元素，则删除它
el :
A .inrt (i , b ) #没找到等于b 的元素，则把b 插⼊到A 中
for a in A :
print (a , end =' ')
测试⽤例
1. 题⽬描述给出的测试⽤例覆盖了⼀个简单的情形。
2. 集合A的元素个数n=10，测试性能。
下⾯不列出输⼊数据和输出数据——规模太⼤了，⽽是给出⽣成集合A和集合B的数据的代码。运⾏以下代码，将⽣成包含10个元素的集合A和20个元素的集合B，存⼊⽂件内。采⽤输⼊重定向，运⾏上⾯⼀节给出的代码（⽂件命名为
tab.py），命令是：
python tab.py < ，
将把⽂件内的两⾏数据⽤作程序输⼊。
with open("", 'w') as txtfile:
txtfile.write(str(1000000) + ' ')
for large in range(1000000, 500000-1, -1):
txtfile.write(str(large) + ' ')
for less in range(1, 500000):
txtfile.write(str(less) + ' ')
txtfile.write( '\n')
txtfile.write(str(20)+' ')
for i in range(20, 20*20, 20):
txtfile.write(str(i) + ' ')
txtfile.write(str(20*20) + '\n')
66
3. n=1的边界情形。A=B。
样例输⼊
1 2
1 2
样例输出
（注：输出为空）
better me什么意思
4. n=1的边界情形。A不等于B。
transcript样例输⼊
1 2
1 3
样例输出
2 3
5. 容易验证输出的。
样例输⼊
4 2 3 6 8
3 2 6 7
样例输出
3 7 8
⼩结
1. 采⽤常规做法来存储数据，⽐如⽤input().split()得到各个数字（字符串），⼜⽐如⽤list来存储n个整数，会占⽤过多内存。⽤array
存储⼀组整数⽐list节省内存。
∩
2. 计算C = (A − B) ∪ (B − A)，等同于计算C = A ∪ B - A B 。
3. 要注意到，两个集合中的数按照从⼩到⼤的顺序给出。这⼀条件埋伏了优化措施。
4. ⼆分查找是⾼效的查找算法。前提是，元素序列是有序的。
