如何在整数列表中找到重复项并创建重复项的另一个列表?
当前回答
我注意到大多数解决方案的复杂度为O(n * n),对于大型列表来说非常缓慢。所以我想分享一下我写的函数,它支持整数或字符串,在最好的情况下是O(n)。对于一个包含10万个元素的列表,最上面的解决方案需要超过30秒,而我的解决方案只需0.12秒
def get_duplicates(list1):
'''Return all duplicates given a list. O(n) complexity for best case scenario.
input: [1, 1, 1, 2, 3, 4, 4]
output: [1, 1, 4]
'''
dic = {}
for el in list1:
try:
dic[el] += 1
except:
dic[el] = 1
dupes = []
for key in dic.keys():
for i in range(dic[key] - 1):
dupes.append(key)
return dupes
list1 = [1, 1, 1, 2, 3, 4, 4]
> print(get_duplicates(list1))
[1, 1, 4]
或者获得唯一的副本:
> print(list(set(get_duplicates(list1))))
[1, 4]
其他回答
你可以使用iteration_utilities.duplicate:
>>> from iteration_utilities import duplicates
>>> list(duplicates([1,1,2,1,2,3,4,2]))
[1, 1, 2, 2]
或者如果你只想要一个副本,可以结合iteration_utilities.unique_everseen:
>>> from iteration_utilities import unique_everseen
>>> list(unique_everseen(duplicates([1,1,2,1,2,3,4,2])))
[1, 2]
它也可以处理不可哈希的元素(但是以性能为代价):
>>> list(duplicates([[1], [2], [1], [3], [1]]))
[[1], [1]]
>>> list(unique_everseen(duplicates([[1], [2], [1], [3], [1]])))
[[1]]
这是只有少数其他方法可以处理的问题。
基准
我做了一个快速的基准测试,其中包含了这里提到的大部分(但不是全部)方法。
第一个基准测试只包含了很小范围的列表长度,因为一些方法具有O(n**2)行为。
在图表中,y轴代表时间,所以值越低越好。它还绘制了log-log,以便更好地可视化广泛的值范围:
除去O(n**2)方法,我在一个列表中做了另一个多达50万个元素的基准测试:
正如您所看到的iteration_utilities。duplicate方法比任何其他方法都快,甚至连链接unique_everseen(duplicate(…))也比其他方法更快或同样快。
这里需要注意的另一件有趣的事情是,熊猫方法对于小列表非常慢,但可以轻松地竞争较长的列表。
然而,由于这些基准测试显示大多数方法的性能大致相同,因此使用哪一种并不重要(除了有O(n**2)运行时的3种方法)。
from iteration_utilities import duplicates, unique_everseen
from collections import Counter
import pandas as pd
import itertools
def georg_counter(it):
return [item for item, count in Counter(it).items() if count > 1]
def georg_set(it):
seen = set()
uniq = []
for x in it:
if x not in seen:
uniq.append(x)
seen.add(x)
def georg_set2(it):
seen = set()
return [x for x in it if x not in seen and not seen.add(x)]
def georg_set3(it):
seen = {}
dupes = []
for x in it:
if x not in seen:
seen[x] = 1
else:
if seen[x] == 1:
dupes.append(x)
seen[x] += 1
def RiteshKumar_count(l):
return set([x for x in l if l.count(x) > 1])
def moooeeeep(seq):
seen = set()
seen_add = seen.add
# adds all elements it doesn't know yet to seen and all other to seen_twice
seen_twice = set( x for x in seq if x in seen or seen_add(x) )
# turn the set into a list (as requested)
return list( seen_twice )
def F1Rumors_implementation(c):
a, b = itertools.tee(sorted(c))
next(b, None)
r = None
for k, g in zip(a, b):
if k != g: continue
if k != r:
yield k
r = k
def F1Rumors(c):
return list(F1Rumors_implementation(c))
def Edward(a):
d = {}
for elem in a:
if elem in d:
d[elem] += 1
else:
d[elem] = 1
return [x for x, y in d.items() if y > 1]
def wordsmith(a):
return pd.Series(a)[pd.Series(a).duplicated()].values
def NikhilPrabhu(li):
li = li.copy()
for x in set(li):
li.remove(x)
return list(set(li))
def firelynx(a):
vc = pd.Series(a).value_counts()
return vc[vc > 1].index.tolist()
def HenryDev(myList):
newList = set()
for i in myList:
if myList.count(i) >= 2:
newList.add(i)
return list(newList)
def yota(number_lst):
seen_set = set()
duplicate_set = set(x for x in number_lst if x in seen_set or seen_set.add(x))
return seen_set - duplicate_set
def IgorVishnevskiy(l):
s=set(l)
d=[]
for x in l:
if x in s:
s.remove(x)
else:
d.append(x)
return d
def it_duplicates(l):
return list(duplicates(l))
def it_unique_duplicates(l):
return list(unique_everseen(duplicates(l)))
基准1
from simple_benchmark import benchmark
import random
funcs = [
georg_counter, georg_set, georg_set2, georg_set3, RiteshKumar_count, moooeeeep,
F1Rumors, Edward, wordsmith, NikhilPrabhu, firelynx,
HenryDev, yota, IgorVishnevskiy, it_duplicates, it_unique_duplicates
]
args = {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(2, 12)}
b = benchmark(funcs, args, 'list size')
b.plot()
基准2
funcs = [
georg_counter, georg_set, georg_set2, georg_set3, moooeeeep,
F1Rumors, Edward, wordsmith, firelynx,
yota, IgorVishnevskiy, it_duplicates, it_unique_duplicates
]
args = {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(2, 20)}
b = benchmark(funcs, args, 'list size')
b.plot()
免责声明
1这是我写的一个第三方库:iteration_utilities。
在没有任何python数据结构的帮助下,你可以简单地尝试下面的代码。这将工作于寻找重复的各种输入,如字符串,列表等。
# finding duplicates in unsorted an array
def duplicates(numbers):
store=[]
checked=[]
for i in range(len(numbers)):
counter =1
for j in range(i+1,len(numbers)):
if numbers[i] not in checked and numbers[j]==numbers[i] :
counter +=1
if counter > 1 :
store.append(numbers[i])
checked.append(numbers[i])
return store
print(duplicates([1,2,2,3,3,3,4,4,5])) # output: [2, 3, 4]
print(duplicates("madam")) # output: ['m', 'a']
方法1:
list(set([val for idx, val in enumerate(input_list) if val in input_list[idx+1:]]))
解释: [val for idx, val in enumerate(input_list) if val in input_list[idx+1:]]是一个列表推导式,它返回一个元素,如果该元素从当前位置存在,则在列表中返回下标。
例子: input_list =[3 42 42岁,31日,31日,31日,31日,5日,6日6日6日6日6日,7日,42)
从索引为0的列表第一个元素42开始,它检查元素42是否存在于input_list[1:]中(即从索引1到列表末尾)。 因为42存在于input_list[1:]中,它将返回42。
然后它转到下一个索引为1的元素31,并检查元素31是否存在于input_list[2:](即从索引2到列表末尾), 因为31存在于input_list[2:]中,它将返回31。
类似地,它遍历列表中的所有元素,只将重复/重复的元素返回到列表中。
然后,因为列表中有重复项,我们需要从每个重复项中选择一个,即从重复项中删除重复项,为此,我们调用python内置的名为set()的函数,它会删除重复项,
然后我们就得到了一个集合,而不是一个列表,因此为了将集合转换为列表,我们使用类型转换,list(),它将元素集转换为列表。
方法2:
def dupes(ilist):
temp_list = [] # initially, empty temporary list
dupe_list = [] # initially, empty duplicate list
for each in ilist:
if each in temp_list: # Found a Duplicate element
if not each in dupe_list: # Avoid duplicate elements in dupe_list
dupe_list.append(each) # Add duplicate element to dupe_list
else:
temp_list.append(each) # Add a new (non-duplicate) to temp_list
return dupe_list
解释: 首先,我们创建两个空列表。 然后继续遍历列表中的所有元素,以查看temp_list(最初为空)中是否存在该元素。如果它不在temp_list中,则使用append方法将它添加到temp_list中。
如果它已经存在于temp_list中,这意味着列表中的当前元素是重复的,因此我们需要使用append方法将它添加到dupe_list中。
一句话解决方案:
set([i for i in list if sum([1 for a in list if a == i]) > 1])
这里有很多答案,但我认为这是一个相对易于阅读和理解的方法:
def get_duplicates(sorted_list):
duplicates = []
last = sorted_list[0]
for x in sorted_list[1:]:
if x == last:
duplicates.append(x)
last = x
return set(duplicates)
注:
如果您希望保留重复计数,请去掉强制转换 'set'在底部获得完整的列表 如果您更喜欢使用生成器,请将duplicate .append(x)替换为yield x和底部的return语句(您可以稍后强制转换为set)
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用pip3安装包时,“Python中的ssl模块不可用”
- 无法切换Python与pyenv
- Python if not == vs if !=
- 如何从scikit-learn决策树中提取决策规则?
- 为什么在Mac OS X v10.9 (Mavericks)的终端中apt-get功能不起作用?
- 将旋转的xtick标签与各自的xtick对齐
- 为什么元组可以包含可变项?
- 如何合并字典的字典?
- 如何创建类属性?
- 不区分大小写的“in”
- 在Python中获取迭代器中的元素个数
- 解析日期字符串并更改格式
- 使用try和。Python中的if
- 如何在Python中获得所有直接子目录