Geek asks and answers

How to find duplicate in list without using set in python?

I know that we can use a set in python to find if there is a duplicate in the list. I'm just wondering if we find a duplicate in the list without using set.

Say my list

a=['1545','1254','1545']

then how to find a duplicate?

+3
source share
7 answers
>>> lis = []
>>> a=['1545','1254','1545']
>>> for i in a:
...     if i not in lis:
...         lis.append(i)
... 
>>> lis
['1545', '1254']
>>> set(a)
set(['1254', '1545'])
+1
source 
a=['1545','1254','1545']
from collections import Counter
print [item for item, count in Counter(a).items() if count != 1]

Output

['1545']

This solution works in O (N). This will be a huge advantage if there are many elements in the list used.

If you just want to find a duplicate list, you can just do

a=['1545','1254','1545']
from collections import Counter
print any(count != 1 for count in Counter(a).values())

As @gnibbler suggested , this would be the fastest solution

from collections import defaultdict
def has_dup(a):
    result = defaultdict(int)
    for item in a:
        result[item] += 1
        if result[item] > 1:
            return True
    else:
        return False

a=['1545','1254','1545']
print has_dup(a)
+2
source

list.count:

In [309]: a=['1545','1254','1545']
     ...: a.count('1545')>1
Out[309]: True
+1

list.count:

>>> a = ['1545','1254','1545']
>>> any(a.count(x) > 1 for x in a) # To check whether there any duplicate
True

>>> # To retrieve any single element that is duplicated
>>> next((x for x in a if a.count(x) > 1), None)
'1545'

# To get duplicate elements (used set literal!)
>>> {x for x in a if a.count(x) > 1}
set(['1545'])
+1

, .

a.sort()
last_x = None
for x in a:
    if x == last_x:
       print "duplicate: %s" % x
       break # existence of duplicates is enough

    last_x = x

O (n log n), n, Counter ( dict ), ).

. . bisect. , .

+1

, , , .count().

dict - , set .

>>> a = ['1545','1254','1545']
>>> D = {}
>>> for i in a:
...     if i in D:
...         print "duplicate", i
...         break
...     D[i] = i
... else:
...     print "no duplicate"
... 
duplicate 1545

groupby, - , .count()

>>> from itertools import groupby
>>> a = ['1545','1254','1545']
>>> next(k for k, g in groupby(sorted(a)) if sum(1 for i in g) > 1)
'1545'
+1

. . :

a=['1545','1254','1545']
d=[]
duplicates=False
for i in a:
    if i not in d:
        d.append(i)
        if len(d)<len(a):
            duplicates=True
        else:
            duplicates=False
print(duplicates)
0

More articles:


All Articles