比较列表以查找python中的公共元素

Question

Possible Duplicate:
Python - Intersection of two lists

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

例如，我遇到的主要问题是两个列表都包含重复的元素

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

使用代码

^{pr2}$

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

我想得到的输出是n = 2，最好不使用集合，我是否可以调整代码，或者用一种新的思考问题的方法来实现这一点？在

谢谢

Answer 1

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

假设我有两个词，"hello"和{}。为了找到公共元素，我可以遍历"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个常用字母。在

Answer 2

以下是一种不使用集合的有效（O(n logn)）方法：

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

不完全清楚您的规范是什么，但是如果您想要A中出现在B中的元素数量，不考虑顺序，而是考虑多重性，请使用^{}：

>>> 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]