面試的時(shí)候被問到這樣一個(gè)問題：有A、B兩個(gè)數(shù)組，找出B中有A中沒有的所有元素（換言之即是求差集B-A）。當(dāng)時(shí)比較緊張，用了最原始的雙重嵌套循環(huán)逐個(gè)比較，很顯然這種時(shí)間復(fù)雜度高達(dá)O(n²)的算法相當(dāng)low。

       回去之后經(jīng)過思考，有了一個(gè)新的思路，即先對(duì)A、B進(jìn)行排序，時(shí)間復(fù)雜度為O（nlog₂n），再對(duì)排序后的數(shù)組同時(shí)遍歷進(jìn)行比較，這里的時(shí)間復(fù)雜度為O（n），這樣總體的時(shí)間復(fù)雜度為O（nlog₂n），效率比之前有了改進(jìn)。（PS：在網(wǎng)上搜索過之后，發(fā)現(xiàn)還有hash的方法可以更簡(jiǎn)單，這里暫不詳敘。）

       于是用剛學(xué)不久的Python來編寫代碼實(shí)現(xiàn)新的思路：

 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=010 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[i]==b[j] :13         i=i+114         j=j+115     elif a[i]>b[j] :16         c.append(b[j])17         j=j+118     elif a[i]<b[j] :19         i=i+120 while j<len(b):21     c.append(b[j])22     j=j+123 print(c)

View Code

       輸出的結(jié)果為：

       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]

       與預(yù)期的結(jié)果一致。

　　PS：這里的代碼有一點(diǎn)小問題，因?yàn)橹坝肞ython3，后來改成了Python2.7，在后者中，print的內(nèi)容不需要括號(hào)，而代碼中多余的括號(hào)并沒有完全移除，這里因?yàn)槊恳痪鋚rint的內(nèi)容只有一個(gè)，所以輸出結(jié)果不會(huì)有差別，但是如果同一句print要輸出多個(gè)元素，就會(huì)出現(xiàn)不同的情況。舉個(gè)例子：

　　print "a","b"

　　print ("a","b")

　　這樣的兩行代碼，在Python3中，前一句會(huì)報(bào)錯(cuò)，后一句會(huì)輸出：a  b 。

　　而在Python2.7中，前一句會(huì)輸出：a b，后一句會(huì)輸出：('a','b')。

       學(xué)習(xí)了一段時(shí)間Python后，發(fā)現(xiàn)了set()這個(gè)數(shù)據(jù)結(jié)構(gòu)。在Python中，set()是一種無序不重復(fù)的數(shù)據(jù)結(jié)構(gòu)，并且可以直接進(jìn)行求交集、并集、差集的步驟。于是，上述問題可以直接這樣寫：

 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=",A10 print "B=",B11 print "Another way to solve it : "12 print list(set(B)-set(A))

View Code

       輸出的結(jié)果為：

　　Another way to solve it :
　　[6, 8, 10, 12, 14, 15, 16, 22]

　　結(jié)果也是正確的。

　　思路很簡(jiǎn)單，把list先轉(zhuǎn)變成set，求差集之后再轉(zhuǎn)回list即可。注意這里用了Python的copy這個(gè)庫(kù)，因?yàn)檫@段代碼和前面的方法實(shí)際上是寫在同一個(gè)程序中，如果直接用A=a，B=b的話，A和B的內(nèi)容將是排序后的a和b。理由是A=a的寫法只是讓A指向a的引用地址，a改變的時(shí)候，A也會(huì)隨之改變；用copy.copy()的話，A才能記錄原始的數(shù)組a。

       用set()的方法只需要一行代碼，相當(dāng)簡(jiǎn)潔，但是這里存在另外一個(gè)問題：假如數(shù)組b中存在著若干個(gè)重復(fù)的元素，且這些元素不存在于數(shù)組a中，而要求的結(jié)果恰好需要重復(fù)的元素也一并列出，并且不能改變?cè)卦跀?shù)組b中出現(xiàn)的順序。比如a=[1,5,2]，b=[2,4,3,3]，按照要求需要輸出[4,3,3]，然而由于set()是不重復(fù)的數(shù)據(jù)結(jié)構(gòu)，如果采取上述方法會(huì)自動(dòng)排序和自動(dòng)剔除重復(fù)的元素，輸出為[3,4]，和要求不符合，那么只能尋找其他的方法了。

　　之后在Operator庫(kù)中找到了方法，代碼如下：

1 import operator2 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

　　輸出的結(jié)果為：

　　Without changing the order:

　　4,3,3

　　這樣即使重復(fù)出現(xiàn)在數(shù)組b中的元素3也能在結(jié)果中同樣重復(fù)出現(xiàn)，元素順序也沒有更改。operator.contains(a,num)語句的作用是判斷num是否在a中，在的話為True，否則為False。

　　最后查看了一下operator的源碼，發(fā)現(xiàn)operator.contains(list,num)函數(shù)的定義僅僅是判斷num in list or not，于是得到了不使用庫(kù)的版本：

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

　　輸出的結(jié)果為：

　　With no modules:

　　4,3,3