高效确定列表中是否有两个相同的三个项目

Question

什么是确定列表中恰好有两个元素相同的最有效方法？例如：

>>> has1dup(["one", "one", "two"])
True
>>> has1dup(["one", "two", "three"])
False
>>> has1dup(["one", "one", "one"])
False

我已经使用if/else语句成功完成了这个任务。然而，如果列表更大，为每对写出每种可能性的任务将变得非常困难和耗时。有没有更快/更简单的方法来完成这个任务？

以下是我尝试过的方法：

def has1dup(lst):
    if lst[0] == lst[1] and lst[1] != lst[2]:
        return True
    elif lst[1] == lst[2] and lst[2] != lst[0]:
        return True
    elif lst[0] == lst[2] and lst[2] != lst[1]:
        return True
    else:
        return False

- JSW189

Answer 1

你可以用一个set来查看有多少个唯一值。如果集合中的项比列表中的项少一个，则其中一个是重复项：

def has1dup(lst):
    return len(lst)-1 == len(set(lst))

- Jochen Ritzel

---

它检查列表中是否恰好有两个相同的项目。但是你不能推广以找到三元组（它们可能只是两对），但这不是问题的关键。 - Jochen Ritzel

+1，和我最终想出来的解决方案一样（在误读问题后），但你的更简洁。 - paxdiablo

只有列表中的元素实现了__hash__（大多数内置类型都是如此），这才有效，但是像has1dup([[1]，[1]，[2]])这样的东西会引发错误，因为列表不可哈希。即使用户定义的对象如果哈希值不是“显著”的话，也不会按预期运行。对于定义为空类的X和Y，has1dup([X()，X()，Y()])返回False。由于问题使用字符串，所以这不应该成为问题。 - jdferreira

这个解决方案是不完整的，因为它假设没有其他具有相同值的项目。然而，对于长度为3的序列，它是可以的，因为确实没有空间容纳其他具有相同值的项目。 - okm

@okm，也许你可以举个例子来说明你的意思。根据我对你在我的答案评论中的回复，我认为这在任何大小的列表上都可以正常工作。 - paxdiablo

@paxdiablo 可能我误解了“列表中恰好有两个元素相同”的意思：如果它的意思是仅有两个具有相同值的元素，那么你和Jochen是正确的。只是我认为它的意思是有两个具有相同值的元素... - okm

Answer 2

>>> from collection import Counter
>>> 2 in Counter(["one", "one", "two"]).values()
True
>>> 2 in Counter(["one", "two", "three"]).values()
False

更新
如果您希望只有两个相同的项目

Counter(seq).values().count(2) == 1

< p > Counter适用于Python 2.7+版本，如果您使用更低版本的Python需要手动实现

def counter(seq): 
    r = {}
    for x in seq:
        r[x] = r.setdefault(x, 0) + 1 # or defaultdict
    return r

- okm

---

我不确定在列表1,1,2,2上是否能正常工作。难道它不应该是“确切地”两个元素吗？ - paxdiablo

抱歉，okm，我已经撤销了我的反对票，因为问题标题确实指定了三个中的两个 - 只有在问题正文中作为附加点提到更长列表的部分。 - paxdiablo

@paxdiablo 没问题，这个问题不是很清晰和明确，我也更新了答案。 - okm

关于你的评论“列表1,1,2,2。它不应该只有两个元素吗？”你是否暗示[1，1，2，2]只能是两个元素或者是负数？我不是母语为英语的人，想确保你话的实际意思。如果是前面那种情况，似乎你自己也有点困惑 =p - okm

我认为1,1,2,2应该返回_false_，因为它没有恰好两个相同的值 - 它实际上有两组两个。所以1,1,2,3,4,5,6,7是true，但1,1,2,2,3,4,5,6,7会返回false。这是我的理解，但正如每个人指出的那样，问题可能需要更清晰明了。 - paxdiablo

Answer 3

你可以使用内置函数 any() 轻松地完成这个操作。

def has_duplicates(seq):
    return any(seq.count(x) > 1 for x in seq)

例子：

>>> has_duplicates([1, 1, 2])
True
>>> has_duplicates([1, 2, 2])
True
>>> has_duplicates([1, 2, 3])
False

如果你只想找到两个且仅有两个相同的项目，那么只需更改条件：

any(seq.count(x) == 2 for x in seq)

如果你想找到只有两个项目的一个实例，我们也可以做到，但需要更多的工作：

def any_n(iterable, n):
    seen = 0
    for value in iterable:
        if value:
            if seen >= n:
                return False
            else:
                seen += 1
    return seen == n

def has_one_value_repeated_n_times(seq, n):
    return any_n((seq.count(x) == n for x in seq), n)

一些快速测试：

tests = [
    [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5],
    [1,2,2,3,3,4,4,4,4,5,5,5,5,5],
    [1,2,2],
    [1,1,2],
    [1,2,3],
]

for test in tests:
    print(test, "-", has_one_value_repeated_n_times(test, 2))

给我们：

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5] - True
[1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5] - False
[1, 2, 2] - True
[1, 1, 2] - True
[1, 2, 3] - False

- Gareth Latty

---

仍然存在与另一个解决方案相同的问题。在这种情况下，列表1,2,2,3,3,3,4,4,4,4,5,5,5,5,5将返回true，对吗？这不完全是两个重复项。即使允许列表大小为三，1,1,1也会对您的函数返回true，尽管它是错误的。 - paxdiablo

尽管您可能需要明确指出这仅适用于三项列表，但可以反转投票。 - paxdiablo

添加了更窄的解决方案。 - Gareth Latty

这是一个O(N^2)的算法。不要在大型列表（例如1000个以上的元素）或性能是一个因素的情况下使用它。 - ninjagecko

@ninjagecko确实，考虑到OP正在谈论长度为3的列表，可能还有更长的列表，我认为性能不会是一个巨大的问题。 - Gareth Latty

Answer 4

2 in collections.Counter(yourList).values()

简短而高效。

如果您的意思是“确切地”指“在元素的多重性中，恰好有一个元素具有多重性2”，那么您可以这样做：

Counter(Counter(yourList).values()).get(2)==1

- ninjagecko

---

"[1,2,2,3,3]" 返回 True，但不符合“恰好”的要求。 - gnr

@mlauria：除非你的意思是“确切地”指“在元素的多重性中，恰好有一个元素的多重性为2”。如果是这种情况：Counter(Counter(yourList).values()).get(2)==1 - ninjagecko

Answer 5

我不懂Python，但这里有一些伪代码：

for i in 0 to length(list):
    j = indexOf(list, list[i], i + 1) > -1

    if j > -1 and indexOf(list, list[i], j + 1) == -1:
        // Found exactly two!

它应该足够高效满足您的需求。

编辑：好的，我把它转成了Python。如果代码不好请见谅。

def exactlyTwo(l):
    for i in xrange(0, len(l)):
        try:
            j = l.index(l[i], i + 1)

            try:
                l.index(l[i], j + 1)
            except ValueError:
                return True
        except ValueError:
            # Do nothing. Not sure how to do that in Python.
            0

    return False

这里有一个演示。

- Ry-

---

顺便说一下，在Python中，"pass"是用来实现这个功能的。 - paxdiablo

Answer 6

你的代码没有问题（至少对于大小为三的列表而言）- 它易读且相当简洁，你只需要在性能成为问题时才真正担心。

像集合转换这样的解决方案比三个条件语句更快的可能性不大，但也不是不可能。

我更喜欢稍微不同的形式来减少“缩进地狱”:-)

if list[0] == list[1] and list[1] != list[2]:
    return True

if list[1] == list[2] and list[2] != list[0]:
    return True

if list[0] == list[2] and list[2] != list[1]:
    return True

return False

或者，如果您更喜欢在屏幕/打印输出上一次看到尽可能多的代码：

if list[0] == list[1] and list[1] != list[2]: return True
if list[1] == list[2] and list[2] != list[0]: return True
if list[0] == list[2] and list[2] != list[1]: return True
return False

对于较大的数组，您可以将其转换为集合，并且如果集合的长度比数组的长度少1，则恰好有一个重复项：

>>> a = [1,2,3,4,4,5,6,7]
>>> a
[1, 2, 3, 4, 4, 5, 6, 7]
>>> len(a) == len (set(a)) + 1
True

- paxdiablo

---

还有一个问题是如何处理较大的列表。 - Michael Mior

@MichaelMior，我已经在末尾添加了更大的列表，但问题标题明确说明了两个或三个。正文要求解决方案，其中列表较大，这就是为什么我添加了集合变量。 - paxdiablo

@paxdiablo，后一种解决方案是不完整的，因为它假设没有其他具有相同值的项。 - okm

@okm，不确定我是否理解了。由于集合会删除重复项，因此集合的长度比数组长度少1的唯一情况是数组中的每个元素都是唯一的，除了一个元素有两个条目。任何其他情况都将涉及长度差异而不是1。例如，“1,2,2,2,3”将导致差异为2，“1,2,3”将导致差异为0，“1,2,2,3,3,3,4,4,4,4”将导致差异为6等等。 - paxdiablo

Answer 7

如果只有一个/没有元素被重复，并且您可以将这些元素表示为正整数（例如通过使用字典将“one”映射到1），那么以下解决方案将起作用。

def find_repeated_element(l):
    return reduce(lambda x,y: x^y, l + list(set(l)))

l = [1,1,2]
>>> find_repeated_element(l)
1
l = [1,2,3]
>>> find_repeated_element(l)
0
l = [1,1,1]
>>> find_repeated_element(l)
0

- reducer

Answer 8

由于我们需要进行配对比较，那么使用 itertools.product 创建所有配对比较的序列如何？

from itertools import product

tests = """\
AAB
ABC
ABB
ABA
AAA""".splitlines()

def has_exactly_one_doubled_element(t):
    return sum(map(lambda a:a[0]==a[1], product(t,t))) == 5

for t in tests:
    print t, has_exactly_one_doubled_element(t)

打印：

AAB True
ABC False
ABB True
ABA True
AAA False

那么，我是如何得出数字5的神奇数值的呢？由product返回的成对数据是将每个元素与列表的第二个副本中的元素配对得到的。如果它们三个都不同，则每个元素会自然而然地与自己相等但与其他元素不相等，因此总数为3。如果有两个元素相同，则除了3个匹配项外，两个重复元素在每个方向上都会相互匹配一次，因此将2加上3得到5。如果所有3个元素都相同，则每个元素都将与其他每个元素相匹配，即3 * 3或9个匹配项。

以下是适用于任何长度列表的通用解决方案，以查看是否存在恰好一个重复值（还使用operator.__eq__和itertools.starmap来避免将lambda传递给map）：

from operator import __eq__ as EQ
from itertools import product, starmap

def has_exactly_one_doubled_element(t):
    return sum(starmap(EQ, product(t,t))) == len(t)+2

args = ["ABCD"]*4
tests = map(''.join, product(*args))
for t in tests:
    print t, has_exactly_one_doubled_element(t)

输出：

AAAA False
AAAB False
AAAC False
AAAD False
AABA False
AABB False
AABC True
AABD True
AACA False
AACB True
AACC False
AACD True
AADA False
AADB True
AADC True
AADD False
ABAA False
ABAB False
ABAC True
ABAD True
ABBA False
ABBB False
ABBC True
ABBD True
ABCA True
ABCB True
ABCC True
ABCD False
ABDA True
ABDB True
ABDC False
ABDD True
ACAA False
ACAB True
ACAC False
ACAD True
ACBA True
ACBB True
ACBC True
ACBD False
ACCA False
ACCB True
ACCC False
ACCD True
ACDA True
ACDB False
ACDC True
ACDD True
ADAA False
ADAB True
ADAC True
ADAD False
ADBA True
ADBB True
ADBC False
ADBD True
ADCA True
ADCB False
ADCC True
ADCD True
ADDA False
ADDB True
ADDC True
ADDD False
BAAA False
BAAB False
BAAC True
BAAD True
BABA False
BABB False
BABC True
BABD True
BACA True
BACB True
BACC True
BACD False
BADA True
BADB True
BADC False
BADD True
BBAA False
BBAB False
BBAC True
BBAD True
BBBA False
BBBB False
BBBC False
BBBD False
BBCA True
BBCB False
BBCC False
BBCD True
BBDA True
BBDB False
BBDC True
BBDD False
BCAA True
BCAB True
BCAC True
BCAD False
BCBA True
BCBB False
BCBC False
BCBD True
BCCA True
BCCB False
BCCC False
BCCD True
BCDA False
BCDB True
BCDC True
BCDD True
BDAA True
BDAB True
BDAC False
BDAD True
BDBA True
BDBB False
BDBC True
BDBD False
BDCA False
BDCB True
BDCC True
BDCD True
BDDA True
BDDB False
BDDC True
BDDD False
CAAA False
CAAB True
CAAC False
CAAD True
CABA True
CABB True
CABC True
CABD False
CACA False
CACB True
CACC False
CACD True
CADA True
CADB False
CADC True
CADD True
CBAA True
CBAB True
CBAC True
CBAD False
CBBA True
CBBB False
CBBC False
CBBD True
CBCA True
CBCB False
CBCC False
CBCD True
CBDA False
CBDB True
CBDC True
CBDD True
CCAA False
CCAB True
CCAC False
CCAD True
CCBA True
CCBB False
CCBC False
CCBD True
CCCA False
CCCB False
CCCC False
CCCD False
CCDA True
CCDB True
CCDC False
CCDD False
CDAA True
CDAB False
CDAC True
CDAD True
CDBA False
CDBB True
CDBC True
CDBD True
CDCA True
CDCB True
CDCC False
CDCD False
CDDA True
CDDB True
CDDC False
CDDD False
DAAA False
DAAB True
DAAC True
DAAD False
DABA True
DABB True
DABC False
DABD True
DACA True
DACB False
DACC True
DACD True
DADA False
DADB True
DADC True
DADD False
DBAA True
DBAB True
DBAC False
DBAD True
DBBA True
DBBB False
DBBC True
DBBD False
DBCA False
DBCB True
DBCC True
DBCD True
DBDA True
DBDB False
DBDC True
DBDD False
DCAA True
DCAB False
DCAC True
DCAD True
DCBA False
DCBB True
DCBC True
DCBD True
DCCA True
DCCB True
DCCC False
DCCD False
DCDA True
DCDB True
DCDC False
DCDD False
DDAA False
DDAB True
DDAC True
DDAD False
DDBA True
DDBB False
DDBC True
DDBD False
DDCA True
DDCB True
DDCC False
DDCD False
DDDA False
DDDB False
DDDC False
DDDD False

- PaulMcG

Answer 9

def exactlyTwo(elements):
    return sum(elements.count(i)-1 for i in elements) == 2

适用于不可哈希元素，并且“恰好两个元素”指三元组和两个双数应返回False

- gnr

Answer 10

我会尝试这样写：len(set(my_list)) == 2

但是当有三个元素时，可以做得更好：> python -c 'from timeit import Timer; t1 = Timer("a[0] == a[1] != a[2] or a[0] == a[2] != a[1] or a[1] == a[2] != a[0]", setup="""a=["one","one","two"]"""); t2 = Timer("len(set(a)) == 2", setup="""a=["one","one","two"]"""); print t1.timeit(), t2.timeit()'

0.893960952759 2.28438997269

- minopret

---

这个检查确保列表只包含两个不同的元素，这并不是同一件事情。 - Michael Mior

问题的标题说了三个中的两个，而问题要求最有效率的方法。 > python -c 'from timeit import Timer; t1 = Timer("len(set(a)) == 2", setup="""a=["one","one","two"]"""); t2 = Timer("len(set(a)) == len(a) - 1", setup="""a=["one","one","two"]"""); print t1.timeit(), t2.timeit()' 2.32463097572 2.84631896019 - minopret

完整的问题陈述为“然而，如果列表更大，则编写每个对可能性的所有可能性的任务将变得非常困难和耗时。”并没有提到仅有三个元素的列表。也许需要来自OP的澄清。 - Michael Mior

@Michael，正如所述，title 指出 "三者中的两个"，问题中的示例也是如此。我认为 "如果列表更大" 是一个次要的问题。 - paxdiablo