题目描述

来源
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 $\cap$ 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提交代码后，成功通过。

参考答案

#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，存入1000000nums.txt文件内。采用输入重定向，运行上面一节给出的代码（文件命名为setab.py），命令是：
   　　　　python setab.py < 1000000nums.txt，
   将把文件内的两行数据用作程序输入。

with open("1000000nums.txt", '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')

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

小结

1. 采用常规做法来存储数据，比如用input().split()得到各个数字（字符串），又比如用list来存储n个整数，会占用过多内存。用array存储一组整数比list节省内存。
2. 计算C = (A − B) ∪ (B − A)，等同于计算C = A ∪ B - A $\cap$ B 。
3. 要注意到，两个集合中的数按照从小到大的顺序给出。这一条件埋伏了优化措施。
4. 二分查找是高效的查找算法。前提是，元素序列是有序的。