面试的时候被问到这样一个问题：有A、B两个数组，找出B中有A中没有的所有元素（换言之即是求差集B-A）。当时比较紧张，用了最原始的双重嵌套循环逐个比较，很显然这种时间复杂度高达O(n2)的算法相当low。
回去之后经过思考，有了一个新的思路，即先对A、B进行排序，时间复杂度为O（nlog2n），再对排序后的数组同时遍历进行比较，这里的时间复杂度为O（n），这样总体的时间复杂度为O（nlog2n），效率比之前有了改进。（PS：在网上搜索过之后，发现还有hash的方法可以更简单，这里暂不详叙。）
于是用刚学不久的Python来编写代码实现新的思路：
1a=[1,2,3,4,5,7,9,11,19,17]2b=[1,2,4,5,6,8,10,12,14,22,16,15]34a.sort()5b.sort()6PRint"sorted a=",a7print"sorted b=",b89i=0，j=010print("The numbers which are in list b but not in list a include:")11whilei<len(a)andj<len(b):12ifa[i]==b[j] :13i=i+114j=j+115elifa[i]>b[j] :16c.append(b[j])17j=j+118elifa[i]<b[j] :19i=i+120whilej<len(b):21c.append(b[j])22j=j+123print(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()是一种无序不重复的数据结构，并且可以直接进行求交集、并集、差集的步骤。于是，上述问题可以直接这样写：
1importcopy23a=[1,2,3,4,5,7,9,11,19,17]4b=[1,2,4,5,6,8,10,12,14,22,16,15]56A=copy.copy(a)7B=copy.copy(b)89print"A=",A10print"B=",B11print"Another way to solve it :"12printlist(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库中找到了方法，代码如下：
1importoperator2a=[1,5,2]3b=[2,4,3,3]45print"Without changing the order :"6fornuminb:7ifoperator.contains(a,num)==False:8printnum,
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，于是得到了不使用库的版本：
1a=[1,5,2]2b=[2,4,3,3]3print"With no modules:"4fornuminb:5ifnumnotina:6printnum,
View Code
输出的结果为：
With no modules:
4,3,3