Python return 列表中的重复项列表

Question

如何快速 return 一个列表的重复项列表，按照它们出现的顺序排列？例如 duplicates([2,3,5,5,5,6,6,3]) results in [5,6,3] 表示重复元素仅在其第二个元素出现时才添加到生成的重复项列表中。到目前为止，我有下面的代码，但它的运行速度不够快，无法通过大型测试用例。没有进口有没有更快的选择？

def duplicates(L):
    first = set()
    second = []
    for i in L:
        if i in first and i not in second:
            second.append(i)
            continue
        if i not in first and i not in second:
            first.add(i)
            continue
    return second

Answer 1

已发布代码的修订

在 OP 代码中 'second' 使用字典而不是列表。
列表字典的查找时间为 O(1) 而不是 O(n)
Dicts 跟踪 Python 3.6+ 的插入顺序或者可以使用 OrderedDict

代码

def duplicatesnew(L):
    first = set()
    second = {}   # Change to dictionary
    for i in L:
        if i in first and i not in second:
            second[i] = None
            continue
        if i not in first and i not in second:
            first.add(i)
            continue

    return list(second.keys())  # report list of keys

    lst = [2,3,5,5,5,6,6,3]

性能

总结

在短名单上相当
在更长的列表上快 2 倍

测试

Use lists of length N

For N = 6: use original list

N > 6 use:

lst = [random.randint(1, 10) for _ in range(N)]

N = 6

原版：2.24 us 修订后：2.74 us
1000个1到10之间的随机数

原文：241 us 修订后：146 us
N = 100, 000

原版：27.2 毫秒修改后：13.4 毫秒

Answer 2

您在使用集合 first 方面做得很好，因为它的 in 操作的时间复杂度为 O(1)。但另一方面，您正在使用 second 的列表，这会将此函数转换为 O(N^2)，在最坏的情况下，您将遍历 second 列表两次.

所以，我对你的建议是使用字典来存储你找到的数字。

例如：

def duplicates(L):
    first = dict()
    second=[]
    for i in L:
        if i not in first:      #First time the number appears
            first[i] = False
        elif not first[i]:      #Number not on the second list
            second.append(i)
            first[i]=True

return second

请注意，我使用布尔值作为字典键值来表示该数字是否出现超过 1 次（或者它是否已添加到 de second 列表）。此解决方案具有 O(N) 时间复杂度，这意味着速度更快。

Python return 列表中的重复项列表

Python return list of duplicates in list in order

python

list

set

duplicates

repeat