Python:最好将字典或哈希图用于数组的常见元素

Question

我必须从2个无序列表中找到共同数字的列表。我有2种方法。有人可以解释哪个更好，为什么

def common_by_dictionary(a1,a2):
    d1 = {}
    for i in a1:
        if not(i in d1):
            d1[i]=1
    for i in a2:
        if (i in d1):
            d1[i]=0
    c = []
    for i in d1:
        if(d1[i]==0):
            c.append(i)
    print c
def common_by_hashmap(a1,a2):
    h = [0]*1000
    for i in a1:
        if not (i in h):
            h[i]=1
    c = []
    for i in a2:
        if(h[i]==1):
            c.append(i)
    print c

common_by_dictionary([1,3,4,6,7,9,12,5],[1,2,4,5,9,10,3])
common_by_hashmap([1,3,4,6,7,9,12,5],[1,2,4,5,9,10,3])

Answer 1

您应该使用set：

def common(first, second):
    return set(first) & set(second)

Answer 2

python中没有哈希地图。本质上的字典是哈希地图的爪哇等效性。您只是在common_by_hashmap功能中使用列表（数组）

Answer 3

第一个更好。在第二部分中，这部分是：

    for i in a1:
        if not (i in h):
            h[i]=1

具有O（n^2）复杂性，因为i in h需要O（n）操作。尽管在这种情况下，N可能是常数1000，但它仍然比查询dict。

要慢得多。

但是，imo，适合您问题的正确方法是使用lim指出的集合：

def common_by_set(a1, a2):
    return list(set(a1) & set(a2))