在一次面試中，我被要求用Python找到兩個串列之間的共同項。我提供了三種解決方案：使用set.intersection、list comprehension和for loop。下面是我做的for回圈：
def common_elements（list1, list2）。
結果 = []
for element in list1:
if element in list2:
result.append(element)
return result
在我做完for回圈后，面試官問我是否有辦法通過不瀏覽串列中的每個專案來減少時間的復雜性。他還暗示我可以先對串列進行排序。我沒能回答這個問題，我還在糾結這個問題。我應該如何處理這個問題呢？
uj5u.com熱心網友回復：
你可以結合一個for-loop和一個迭代器來并行地遍歷已排序的串列，并沿途產生匹配。
def common（L1,L2）。
iter2 = iter(sorted(L2)) # iterator on sorted L2 values[/span]。
Done = object() # 標志以識別迭代結束。
v2 = next(iter2,Done) # 得到L2的第一個（最低）元素。
for v1 in sorted（L1）。
while v2 is not Done and v2<v1。
v2 = next(iter2,Done) # advance in sorted L2 to reach or surpass v1.
if v1 == v2:
yield v1 # return matches
v2 = next(iter2,Done) # advance (only match items once each)
if v2 is Done。break # stop if L2 values exausted
for c in common([3, 7,4,2, 4, 3,1], [4,5, 2,2,4,3]）。)
print(c)
2
3 3
4 4
4 4
這將有一個O(NlogN MlogM)的時間復雜度，而不是O(N*M)，其中N和M是串列大小
。你可以提出的另一個解決方案是使用計數器類，它的復雜度為O(N M)：
from collections import Counter
L1,L2 = [3,7，4。 2,4，3。 1],[4,5, 2,2,4, 3]
c = list((Counter(L1) & Counter(L2)).elements()
print(c) # [3, 4, 4, 2]/span>
uj5u.com熱心網友回復：
正如我在問題評論中提到的，無論是集合還是你的回圈方案都不能處理每個串列中的重復，所以我假設它保證沒有任何重復。
這里有一個生成器版本，對兩個串列進行排序，然后合并它們（使用 heapq.merge）。這樣一來，兩個串列中的共同值就會出現在一起，所以如果一個值與前一個值相同的話，我們就會產生一個值：
def common_elements1（list1, list2）。
list1.sort()
list2.sort()
merged = merge(list1, list2)
prev = next(merged, None)
for x in merged:
if x == prev:
yield x
prev = x
一個黑客式的海象串列編譯版本：
def common_elements2（list1, list2）。
list1.sort()
list2.sort()
merged = merge(list1, list2)
prev = next(merged, None)
return [x for x in merged
if x == prev or not [prev := x]]
或者用itertools.groupby：
def common_elements3（list1, list2）。
list1.sort()
list2.sort()
merged = merge(list1, list2)
return [x for _, [_, *g] in groupby(merged)
for x in g] 。
所有代碼都有測驗。在線試用！
uj5u.com熱心網友回復：
我相信你的問題的答案是雙指標
。這個想法是對兩個串列進行排序，并有一個指標i從l1的開頭開始，j從l2的開頭開始，每次你比較兩個元素，你把最小的元素的指標向前移動，直到其中一個到達終點。
def findCommon（l1,l2）。
l1.sort()
l2.sort()
i= 0: l1.sort()
j= 0: l1.sort()
res = []
while i < len(l1) and j < len（l2）。
if l1[i] == l2[j]:
res.append(l1[i])
if l1[i] < l2[j]:
i =1
else:
j = 1 else: j = 1
return res
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/325380.html
標籤：
上一篇：洗掉子串列中的字符
下一篇：Java中將字串轉換為鍵值對