从列表中删除唯一值并仅保留重复项

Question

我正在寻找一个id列表并返回一个多次出现的id列表.这就是我设置的工作方式:

singles = list(ids)
duplicates = []
while len(singles) > 0:
    elem = singles.pop()
    if elem in singles:
        duplicates.append(elem)

但是id列表可能会变得很长,而且我实际上不希望在一个昂贵的len调用上使用while循环,如果我可以避免它.(我可以走不优雅的路线并且调用len一次,然后在每次迭代时减少它,但是如果可以的话我宁愿避免它).

Answer 1

这样做的明智之举是使用一种简单有效的数据结构,例如Counter:

>>> ids = [random.randrange(100) for _ in range(200)]
>>> from collections import Counter
>>> counts = Counter(ids)
>>> dupids = [id for id in ids if counts[id] > 1]

构建CounterO(N)时间,而不是O(N log N)时间进行排序,或O(N ^ 2)每次从头开始计算每个元素.

作为旁注:

但是id列表可能会变得很长,而且我实际上不希望在一个昂贵的len调用上使用while循环,如果我可以避免它.

len不贵.它是恒定的时间,并且(至少在内置类型列表中list)它的速度与函数可能在Python中完全没有做任何事情一样快.

代码中昂贵的部分是elem in singles在循环内部调用- 这意味着对于每个元素,您必须将它与可能的每个其他元素进行比较,这意味着二次时间.

Answer 2

你可以这样做,

>>> ids = [1,2,3,2,3,5]
>>> set(i for i in ids if ids.count(i) > 1)
{2, 3}