如何查找两个列表中共同元素？

Question

编写一个函数commonElements(a1, a2)，该函数接受两个元组作为参数，并返回一个排序后的元组，其中包含在这两个元组中都出现的元素。

我的任务是：

    >>> commonElements((1, 2, 3), (2, 5, 1))
    (1, 2)
    >>> commonElements((1, 2, 3, 'p', 'n'), (2, 5 ,1, 'p'))
    (1, 2, 'p')
    >>> commonElements((1, 3, 'p', 'n'), ('a', 2 , 5, 1, 'p'))
    (1, 'p')

我尝试以这种方式完成它。

def commonElements(a1, a2):
    return tuple(set(a1).intersection( set(a2) ))

有人知道我在需求方面犯了什么错误吗？
我无法通过。

- newbie

---

我不明白你的问题在哪里。这似乎是在做你所要求的事情。 - Ben

@Ben 他也这么认为。那个是他的问题，因为有人（他的老师？）认为他的答案不正确。 - John

这是一个很好的作业问题提问示例，因为您展示了自己的尝试并询问了特定问题。但请注意，作业问题应标记为“homework”。 - ninjagecko

@John，好的。我没有注意到排序要求。 - Ben

Answer 1

def commonElements(a1, a2):
     return tuple(sorted(set(a1).intersection( set(a2) )))

- kontulai

Answer 2

您忘记了排序要求吗？

编辑

显然，set按升序对其元素进行排序，但这可能是一个实现细节。如果您被要求编写此函数作为测试，则可能需要自己实现整个函数而不是委托给set？

编辑2

为了完整起见，以下是应满足要求的实现：

def commonElements(a1, a2):
    common = []
    for x in a1:
        if x in a2:
            common.append(x)
    common.sort()
    return tuple(common)

- aknuds1

Answer 3

集合是无序的。因此，结果的顺序可能是任意的。 我会得出这样的结果：

def commonElements(a1, a2):
    L = []
    for el in a1:
        if el in a2:
            L.append(el)
    return tuple(L)

请注意，这种解决问题的方法会按照元组a1中的顺序获取输出元素。因此，正如评论中提到的那样，更正确的叫法是“排序”，而不是“排序”。 此外，它的复杂度为O(n*m)，其中n和m分别是列表a1和a2的长度。

如果需要在本例中实现O(n*log(m))，可以使用bisect模块来访问第二个元组a2的元素（在进行之前应该对其进行排序）。

如果需要常规排序，我会使用您的代码，并稍作修改：

def commonElements(a1, a2):
    return tuple(sorted(set(a1).intersection(set(a2))))

平均而言，它的复杂度为O(min(m+n)*log(min(n+m)))（由于排序），最坏情况下是O(n*m)，因为存在交集。

如果需要在不使用set的情况下实现代码（例如出于学习目的），以下是代码：

def commonElements(a1, a2):
    L = []
    for el in a1:
        if el in a2:
            L.append(el)
    L.sort()
    return tuple(L)

复杂度为O(n*m)。

使用bisect后的代码如下：

from bisect import bisect_left
def commonElements(a1, a2):
   L = []
   a2.sort() #sort a2 to be able to use binary search in the internal loop thus changing the complexity from O(n^2) to O(n*log(n)) (assuming n and m are rather equal).
   a2_len = len(a2)
   for el in a1:
       i = bisect_left(a2, el)
       if i != a2_len and a2[i] == el:
           L.append(x)
   # L.sort() #uncomment this line if the list in sorted order is needed (not just ordered as the first lits; it's possible to sort a1 in the very beginning of the function, but that would be slower on the average since L is smaller on the average than a1 or a2 (since L is their intersection).
   return tuple(L)

复杂度为 O(n*log(m))。

- ovgolovin

---

假设元组a1按顺序开始排序。这是“好”的O(N)方法，而不是交集然后排序的方法（虽然它足够好，但只有O(N log(N))），但您必须说明非常强的前提条件，即a1已排序。即使有“a1必须排序”的假设，这仍将与原始问题不符。如果附带说明，则很高兴删除-1。 - ninjagecko

哎呀！结果应该是一个元组。我会更正代码。 - ovgolovin

@ninjagecko 难道不是O(N^2)吗？if el in a2本身不就是一次搜索吗？ - Manny D

如果我正确理解了任务，那么顺序应该与第一个元组保持一致。 - ovgolovin

如果“排序”意味着应用传统排序，我会坚持问题中提供的稍微更正的变体：return tuple(sorted(list(set(a1).intersection(set(a2))))))。 - ovgolovin

Answer 4

这个程序对我来说似乎是有效的。python-2.7.1+。

然而，需要提到的是，集合按定义是“无序”的。因此，“交集”得到的集合也将是无序的。

要将其转换为元素有序的元组，需要额外的代码。

可能需要类似以下的代码：

def commonElements(a1, a2):
    intersection = list(set(a1).intersection(set(a2)))
    intersection.sort()
    return tuple(intersection)

http://docs.python.org/library/sets.html,

- ksrikanth

Answer 5

另一个简短的示例解决方案。这是我会写的方式。最短的解决方案？

def commonElements(a1, a2):
     return tuple(sorted([x for x in a1 if x in a2]))

- Carl F.