查找两个列表之间的交集大小

Question

我正在尝试编写一个函数，returns 两个列表之间的共同元素的数量。如果元素在 L1 中出现 j 次，在 L2 中出现 k 次，则共享 j 和 k 元素中的最小值。

示例：

L1 = [1, 2, 3, 4, 5]
L2 = [4, 2]
L3 = [1, 2, 3, 4, 4, 5, 5]
intersection_size ( L1 , L2 ) => 2
intersection_size ( L1 , L3 ) => 5

我的想法是将L1和L2按升序排序，然后比较每个元素：

def intersection(L1, L2):
    dL1 = L1[:]
    dL2 = L2[:]
    dL1.sort()
    dL2.sort()
    if dL1[1:] == [] or dL2[1:] == []:
        return 0
    if dL1[0] == dL2[0]:
        return 1 + intersection(dL1[1:], dL2[1:])
    elif dL1[0] > dL2[0]:
        return 0 + intersection(dL1, dL2[1:])
    elif dL1[0] < dL2[0]:
        return 0 + intersection(dL1[1:], dL2)

然而，当我测试 intersection([1, 6, 1, 4], [1, 2, 3, 4]) 时，函数给了我 1 而不是 2。谁能告诉我哪一部分是错误的？

我创建了 dL1 和 dL2，因为我希望 L1 和 L2 保持不变以用于其他目的，并且由于我是初学者，所以我' m 只允许使用基本递归和抽象列表函数来执行此操作。

Answer 1

以下将起作用

len(set(L1) & set(L3))

如果您不想使用sets，您可以执行以下操作：

def intersection(L1, L2):
    return len([x for x in L1 if x in L2])

Answer 2

这部分逻辑错误：

    if dL1[1:] == [] or dL2[1:] == []:
        return 0

基本情况应该是一个或两个列表都为空。但是当一个或两个列表只有一个元素时，您将返回 0。这是不正确的，因为该元素仍然可以匹配，因此交集的大小不会为 0。如果将此条件更改为 dL1 == [] or dL2 == []，则它有效：

>>> intersection(L1, L2)
2
>>> intersection(L1, L3)
5
>>> intersection([1, 6, 1, 4], [1, 2, 3, 4])
2
>>> intersection([1, 1, 1, 2, 2], [1, 1, 2, 2, 2])
4

查找两个列表之间的交集大小

Find the size of intersection between two lists

python

recursion

list

set-intersection