比较列表以查找python中的常见元素

Question

可能重复： Python - Intersection of two lists

我试图比较两个列表，以找出它们共有的元素数。

我遇到的主要问题是，当任何一个列表包含重复的元素时，例如

A = [1,1,1,1]   and  
B = [1,1,2,3]

使用代码

n = 0
for x in A:
   if x in B:
      n += 1
print n

给出n = 4的输出，因为技术上A的所有元素都在B中

我想得到n = 2的输出，最好不使用get，我是否可以修改我的代码，或者用一种新的思路来解决这个问题呢？

谢谢

Answer 1

还不完全清楚您的规范是什么，但是如果您想要在A中显示在B中的元素数量，而不考虑顺序，但要考虑多样性，请使用collections.Counter

>>> from collections import Counter
>>> A = [1,1,1,1]
>>> B = [1,1,2,3]
>>> C = Counter(A) & Counter(B)
>>> sum(C.itervalues())
2
>>> list(C.elements())
[1, 1]

Answer 2

下面是一种高效(O(n logn))的方法，可以不使用sets：

def count_common(a, b):
  ret = 0
  a = sorted(a)
  b = sorted(b)
  i = j = 0
  while i < len(a) and j < len(b):
    c = cmp(a[i], b[j])
    if c == 0:
      ret += 1
    if c <= 0:
      i += 1
    if c >= 0:
      j += 1
  return ret

print count_common([1,1,1,1], [1,1,2,3])

如果您的列表总是被排序，就像在您的示例中一样，您可以删除这两个sorted()调用。这将给出一个O(n)算法。

Answer 3

这是一种完全不同的思考这个问题的方式。

想象一下我有两个词，"hello"和"world"。为了找到常见的元素，我可以迭代"hello"，给我['h', 'e', 'l', 'l', 'o']。对于列表中的每个元素，我将从第二个list(word)中删除它。

1. 'h'在['w', 'o', 'r', 'l', 'd']吗？不是的。
2. 'e'在['w', 'o', 'r', 'l', 'd']吗？不是的。
3. 'l'在['w', 'o', 'r', 'l', 'd']吗？是!
4. 把它从"world"上删除，给我['w', 'o', 'r', 'd']。
5. 'l'在['w', 'o', 'r', 'd']吗？不是的。
6. 'o'在['w', 'o', 'r', 'd']吗？
7. 是!把它去掉，['w', 'o', 'r', 'd']，给我['w', 'r', 'd']

将原始对象的长度(确保您已经保存了一份副本)与新生成的对象进行比较，您将看到2的差异，指示2个普通字母。