Python ⼊门习题（80）——OpenJudge 百练习题：集合运算
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集合中所包含的整数。
请将这些整数按照从⼩到⼤的顺序排序。
样例输⼊
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（即set 类型）。同样步骤得到集合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  bisect
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 ()
A .pop (0)
B .pop (0)
# t1 = time.process_time()
# print("输⼊累计时间：", t1 - t0)
for  b in  B :
i = bisect .bisect_left (A , b )  #⼆分查，集合A 中第⼀个⼤于等于b 的元素的索引
if  i != len (A ) and  A [i ] == b :
A .pop (i )  #在集合A 中到等于b 的元素，则删除它
else :
A .insert (i , b )  #没到等于b 的元素，则把b 插⼊到A 中
for  a in  A :
print (a , end =' ')
测试⽤例
1. 题⽬描述给出的测试⽤例覆盖了⼀个简单的情形。
2. 集合A的元素个数n=10，测试性能。
下⾯不列出输⼊数据和输出数据——规模太⼤了，⽽是给出⽣成集合A和集合B的数据的代码。运⾏以下代码，将⽣成包含10个元素的集合A和20个元素的集合B，存⼊⽂件内。采⽤输⼊重定向，运⾏上⾯⼀节给出的代码（⽂件命名为
setab.py），命令是：
    python setab.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
样例输出
（注：输出为空）
4. n=1的边界情形。A不等于B。
样例输⼊
1 2
1 3
样例输出
2 3
5. 容易验证输出的。
样例输⼊
4 2 3 6 8
3 2 6 7
样例输出
3 7 8
python新手代码练习
⼩结
1. 采⽤常规做法来存储数据，⽐如⽤input().split()得到各个数字（字符串），⼜⽐如⽤list来存储n个整数，会占⽤过多内存。⽤array
存储⼀组整数⽐list节省内存。
∩
2. 计算C = (A − B) ∪ (B − A)，等同于计算C = A ∪ B - A    B 。
3. 要注意到，两个集合中的数按照从⼩到⼤的顺序给出。这⼀条件埋伏了优化措施。
4. ⼆分查是⾼效的查算法。前提是，元素序列是有序的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。