CODEWITHSUNDEEP
python
user3260982
user3260982

Reputation:

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

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

Say, my list is 

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

then how to find a duplicate?

Upvotes: 3

Views: 552

Answers (8)

squillero
squillero

Reputation: 5

Without using sets...

original = ['1545','1254','1545']

# Non-duplicated elements
>>> [x for i, x in enumerate(original) if i == original.index(x)]
['1545', '1254']

# Duplicated elements
>>> [x for i, x in enumerate(original) if i != original.index(x)]
['1545']

Upvotes: 0

user3260982
user3260982

Reputation:

thanks all for working on this problem. I also got to learn a lot from different answers. This is how I have answered:

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)

Upvotes: 0

John La Rooy
John La Rooy

Reputation: 304147

If this is homework, your teacher is probably asking for the hideously inefficient .count() style answer.

In practice using a dict is your next best bet if set is disallowed.

>>> 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

Here is a version using groupby which is still much better that the .count() method

>>> 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'

Upvotes: 1

thefourtheye
thefourtheye

Reputation: 239463

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

Output

['1545']

This solution runs in O(N). This will be a huge advantage if the list used has a lot of elements.

If you just want to find if the list has duplicates, you can simply 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 practically 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)

Upvotes: 2

demented hedgehog
demented hedgehog

Reputation: 7538

sort the list and check that the next value is not equal to the last one..

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

This should be O(n log n) which is slower for big n than the Counter solution (but counter uses a dict under the hood.. which is not too dissimilar from a set really).

An alternative is to insert the elements and keep the list sorted.. see the bisect module. It makes your inserts slower but your check for duplicates fast.

Upvotes: 1

Tanveer Alam
Tanveer Alam

Reputation: 5275

>>> 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'])

Upvotes: 2

falsetru
falsetru

Reputation: 369064

Using list.count:

>>> a = ['1545','1254','1545']
>>> any(a.count(x) > 1 for x in a) # To check whether there's 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'])

Upvotes: 1

zhangxaochen
zhangxaochen

Reputation: 34017

use list.count:

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

Upvotes: 1

Related Questions