Python学习笔记（1）——数组差集

hanling

　　面试的时候被问到这样一个问题：有A、B两个数组，找出B中有A中没有的所有元素（换言之即是求差集B-A）。当时比较紧张，用了最原始的双重嵌套循环逐个比较，很显然这种时间复杂度高达O(n2)的算法相当low。
　　回去之后经过思考，有了一个新的思路，即先对A、B进行排序，时间复杂度为O（nlog2n），再对排序后的数组同时遍历进行比较，这里的时间复杂度为O（n），这样总体的时间复杂度为O（nlog2n），效率比之前有了改进。（PS：在网上搜索过之后，发现还有hash的方法可以更简单，这里暂不详叙。）
　　于是用刚学不久的Python来编写代码实现新的思路：





1 a=[1,2,3,4,5,7,9,11,19,17]
2 b=[1,2,4,5,6,8,10,12,14,22,16,15]
3
4 a.sort()
5 b.sort()
6 print "sorted a=",a
7 print "sorted b=",b
8
9 i=0，j=0
10 print ("The numbers which are in list b but not in list a include:")
11 while i<len(a) and j<len(b):
12     if a==b[j] :
13         i=i+1
14         j=j+1
15     elif a>b[j] :
16         c.append(b[j])
17         j=j+1
18     elif a<b[j] :
19         i=i+1
20 while j<len(b):
21     c.append(b[j])
22     j=j+1
23 print(c)
View Code　　输出的结果为：
　　sorted a= [1, 2, 3, 4, 5, 7, 9, 11, 17, 19]
       sorted b= [1, 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 22]
       The numbers which are in list b but not in list a include:
       [6, 8, 10, 12, 14, 15, 16, 22]
　　与预期的结果一致。
　　PS：这里的代码有一点小问题，因为之前用Python3，后来改成了Python2.7，在后者中，print的内容不需要括号，而代码中多余的括号并没有完全移除，这里因为每一句print的内容只有一个，所以输出结果不会有差别，但是如果同一句print要输出多个元素，就会出现不同的情况。举个例子：
　　print "a","b"
　　print ("a","b")
　　这样的两行代码，在Python3中，前一句会报错，后一句会输出：a  b 。
　　而在Python2.7中，前一句会输出：a b，后一句会输出：('a','b')。

　　学习了一段时间Python后，发现了set()这个数据结构。在Python中，set()是一种无序不重复的数据结构，并且可以直接进行求交集、并集、差集的步骤。于是，上述问题可以直接这样写：





1 import copy
2
3 a=[1,2,3,4,5,7,9,11,19,17]
4 b=[1,2,4,5,6,8,10,12,14,22,16,15]
5
6 A=copy.copy(a)
7 B=copy.copy(b)
8
9 print "A=",A
10 print "B=",B
11 print "Another way to solve it : "
12 print list(set(B)-set(A))
View Code　　输出的结果为：
　　Another way to solve it :
　　[6, 8, 10, 12, 14, 15, 16, 22]
　　结果也是正确的。
　　思路很简单，把list先转变成set，求差集之后再转回list即可。注意这里用了Python的copy这个库，因为这段代码和前面的方法实际上是写在同一个程序中，如果直接用A=a，B=b的话，A和B的内容将是排序后的a和b。理由是A=a的写法只是让A指向a的引用地址，a改变的时候，A也会随之改变；用copy.copy()的话，A才能记录原始的数组a。

　　用set()的方法只需要一行代码，相当简洁，但是这里存在另外一个问题：假如数组b中存在着若干个重复的元素，且这些元素不存在于数组a中，而要求的结果恰好需要重复的元素也一并列出，并且不能改变元素在数组b中出现的顺序。比如a=[1,5,2]，b=[2,4,3,3]，按照要求需要输出[4,3,3]，然而由于set()是不重复的数据结构，如果采取上述方法会自动排序和自动剔除重复的元素，输出为[3,4]，和要求不符合，那么只能寻找其他的方法了。
　　之后在operator库中找到了方法，代码如下：





1 import operator
2 a=[1,5,2]
3 b=[2,4,3,3]
4
5 print "Without changing the order :"
6 for num in b:
7     if operator.contains(a,num)==False:
8         print num,
View Code　　输出的结果为：
　　Without changing the order:
　　4,3,3
　　这样即使重复出现在数组b中的元素3也能在结果中同样重复出现，元素顺序也没有更改。operator.contains(a,num)语句的作用是判断num是否在a中，在的话为True，否则为False。

　　最后查看了一下operator的源码，发现operator.contains(list,num)函数的定义仅仅是判断num in list or not，于是得到了不使用库的版本：





1 a=[1,5,2]
2 b=[2,4,3,3]
3 print "With no modules:"
4 for num in b:
5     if num not in a:
6         print num,
View Code　　输出的结果为：
　　With no modules:
　　4,3,3