例如,给定列表['one', 'two', 'one'],算法应该返回True,而给定['one', 'two', 'three']则应该返回False。
当前回答
我发现这是最好的性能,因为当它发现第一个复制时,它会短路操作,那么这个算法的时间和空间复杂度为O(n),其中n是列表的长度:
def has_duplicated_elements(iterable):
""" Given an `iterable`, return True if there are duplicated entries. """
clean_elements_set = set()
clean_elements_set_add = clean_elements_set.add
for possible_duplicate_element in iterable:
if possible_duplicate_element in clean_elements_set:
return True
else:
clean_elements_set_add( possible_duplicate_element )
return False
其他回答
def check_duplicates(my_list):
seen = {}
for item in my_list:
if seen.get(item):
return True
seen[item] = True
return False
仅推荐用于短列表:
any(thelist.count(x) > 1 for x in thelist)
不要在一个很长的列表上使用——它所花费的时间与列表中项目数量的平方成正比!
对于具有可哈希项(字符串,数字和c)的较长列表:
def anydup(thelist):
seen = set()
for x in thelist:
if x in seen: return True
seen.add(x)
return False
如果你的项目是不可哈希的(子列表,字典等),它会变得更加复杂,尽管它仍然有可能得到O(N logN),如果它们至少具有可比性。但你需要知道或测试项目的特征(可哈希与否,可比性与否),以获得最佳性能——可哈希对象为O(N),不可哈希对象为O(N log N),否则就会变成O(N平方),没有人能做什么:-(。
如果所有值都是可哈希的,使用set()删除重复项:
>>> your_list = ['one', 'two', 'one']
>>> len(your_list) != len(set(your_list))
True
如果您喜欢函数式编程风格,这里有一个有用的函数,使用doctest自文档和测试代码。
def decompose(a_list):
"""Turns a list into a set of all elements and a set of duplicated elements.
Returns a pair of sets. The first one contains elements
that are found at least once in the list. The second one
contains elements that appear more than once.
>>> decompose([1,2,3,5,3,2,6])
(set([1, 2, 3, 5, 6]), set([2, 3]))
"""
return reduce(
lambda (u, d), o : (u.union([o]), d.union(u.intersection([o]))),
a_list,
(set(), set()))
if __name__ == "__main__":
import doctest
doctest.testmod()
从这里你可以通过检查返回对的第二个元素是否为空来测试唯一性:
def is_set(l):
"""Test if there is no duplicate element in l.
>>> is_set([1,2,3])
True
>>> is_set([1,2,1])
False
>>> is_set([])
True
"""
return not decompose(l)[1]
注意,这并不有效,因为您是显式地构造分解。但是在使用reduce的过程中,你可以得到一些等价的(但效率稍低)答案5:
def is_set(l):
try:
def func(s, o):
if o in s:
raise Exception
return s.union([o])
reduce(func, l, set())
return True
except:
return False
另一种简洁的方法是使用Counter。
要确定原始列表中是否有重复项:
from collections import Counter
def has_dupes(l):
# second element of the tuple has number of repetitions
return Counter(l).most_common()[0][1] > 1
或者获取重复项的列表:
def get_dupes(l):
return [k for k, v in Counter(l).items() if v > 1]
推荐文章
- 如何从psycopg2游标获得列名列表?
- Python中dict对象的联合
- Java中的split()方法对点(.)不起作用。
- 如何有效地比较两个无序列表(不是集合)?
- 如何在交互式Python中查看整个命令历史?
- 我如何检查如果一个变量是JavaScript字符串?
- 如何显示有两个小数点后的浮点数?
- 如何用OpenCV2.0和Python2.6调整图像大小
- 在每个列表元素上调用int()函数?
- 将Set<T>转换为List<T>的最简洁的方法
- 在Lua中拆分字符串?
- 当使用代码存储库时,如何引用资源的相对路径
- 如何在Flask-SQLAlchemy中按id删除记录
- 在Python中插入列表的第一个位置
- 在javascript中从平面数组构建树数组