從兩個列表中包含的元素的聯合設置

Question

這是面試前的提問者。我相信我有答案只是想得到確認即時通訊的權利。

第1部分 - 告訴我這段代碼做什麼，以及它的大O性能 2部分 - 自己重新寫出來，告訴我你的解決方案

def foo(a, b): 
    """ a and b are both lists """ 
    c = [] 
    for i in a: 
     if is_bar(b, i): 
      c.append(i) 
    return unique(c) 

    def is_bar(a, b): 
    for i in a: 
     if i == b: 
      return True 
    return False 

    def unique(arr): 
    b = {} 
    for i in arr: 
     b[i] = 1 

    return b.keys() 

答案的大O性能： 它從兩個列表中包含的元素的聯合創建一個集合。它大O性能是O（n2）的

我的解決方案，我相信達到O（n）的

Set A = getSetA(); 
Set B = getSetB(); 

Set UnionAB = new Set(A); 
UnionAB.addAll(B); 

for (Object inA : a) 
    if(B.contains(inA)) 
     UnionAB.remove(inA); 

Answer 1

好像原來的代碼是幹什麼的交集不是工會。它遍歷第一個列表（a）中的所有元素並檢查它是否存在於第二個列表（b）中，在這種情況下，它將它添加到列表c中。然後它返回c中的獨特元素。 O（n^2）的表現看起來是正確的。