对数组进行排序。然后使用两个指针遍历它们，始终使一个指针指向较小的值。当它们指向相等的值时，您将拥有一个共同的价值。这将是O（n +
m），其中n和m是两个列表的大小。就像在merge
sort中进行合并一样，但是只有在所指向的值相等时才产生输出。

def common_elements(a, b):
  a.sort()
  b.sort()
  i, j = 0, 0
  common = []
  while i < len(a) and j < len(b):
    if a[i] == b[j]:
      common.append(a[i])
      i += 1
      j += 1
    elif a[i] < b[j]:
      i += 1
    else:
      j += 1
  return common

print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

输出

Common values: 1, 4

如果元素不可比较，则将一个列表中的元素放入哈希图中，然后对照哈希图检查第二个列表中的元素。