3

可能重复：
Python - 两个列表的交集

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

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

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，最好不使用集合，无论如何我可以调整我的代码，或者一种新的思考问题的方式来实现这一点？

谢谢

4

4 回答 4

6

尚不完全清楚您的规范是什么，但如果您想要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]
于 2012-12-04T20:05:50.243 回答
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)算法。

于 2012-12-04T20:11:10.607 回答
1

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

想象一下，我有两个词，"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 个常见字母。

于 2012-12-04T19:50:17.140 回答
0

所以你想让程序检查两个列表中相同索引处的元素是否相等？那将非常简单：只需遍历两个数组的长度（我认为应该具有相同的长度），例如使用变量 i，然后通过 A.index(i) 和 B 比较每个数组。 index(i) 函数。如果你愿意，我可以发布代码。

如果这不是您想要做的，请务必让您的问题更清楚。

于 2012-12-04T19:43:42.003 回答