如何找到两个其他列表中的每个元素？

问题描述：

编写一个函数commonElements（a1，a2），它接受2个元组作为参数，并返回一个包含元组的元素的排序元组。如何找到两个其他列表中的每个元素？

我的任务是：

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

任何人都知道我的错误与要求是什么？
我不能通过。

我不明白你的问题是什么。这似乎正在做你在问什么。 – Ben

@本他也这么认为。 *那是他的问题，因为其他人（他的老师？）认为他的答案不正确。 – John

这是如何提出作业问题的一个很好的例子，因为您展示了您的尝试并询问了具体问题。但请注意，作业问题应标记为“家庭作业”。 – ninjagecko

答

集不排序。所以结果的顺序可能是任意的。我会想出这样的事情：

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)因为intersection。

如果代码需要在不使用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))。

这假定元组'a1'以排序顺序开始。然而，与“交叉然后排序”方法相比，这是“好”的“O（N）”方式（这很好，只有'O（N log（N））'），但是你已经陈述了“a1”被排序的非常强烈的假设。即使在“a1必须排序”的假设下，这对每个原始问题仍然是不正确的。如果警告声明，很乐意删除-1。 – ninjagecko

糟糕！结果应该是一个元组。我会更正代码。 – ovgolovin

@ninjagecko难道不是O（N^2）吗？ '如果el在a2'本身就是搜索，不是吗？ –

答

你忘了排序要求？

编辑

显然，组对其进行排序按升序排列元素，但是这可能是一个实现细节。如果你被要求写这个函数作为测试，也许你需要实现整个事情，而不是委托设置？

EDIT 2

为了完整起见，应符合要求的实现：

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

答

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

答

该程序似乎为我工作。蟒蛇-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，

答

另一个短例子溶液沿着线。这就是我如何写它。最短的解决方案？

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

如何找到两个其他列表中的每个元素？

相关推荐