Как найти дубликат в списке без использования набора в python?

Question

Я знаю, что мы можем использовать набор в python, чтобы найти, есть ли дубликат в списке. Мне просто интересно, если мы найдем дубликат в списке без использования set.

Скажем, мой список

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

тогда как найти дубликат?

Answer 1

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

Answer 2

использование list.count:

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

Answer 3

Использование 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']) 

Answer 4

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

Выходной

['1545'] 

Это решение RU ns в O (N). Это будет огромным преимуществом, если в списке используется много элементов.

Если вы просто хотите, чтобы найти, если в списке есть дубликаты, вы можете просто сделать

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

Как @gnibbler suggested, это будет практически самым быстрым решением

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) 

Answer 5

сортировать список и проверить, что следующее значение не равно последнему.

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. Это делает ваши вставки медленнее, но ваш чек на дубликаты быстро.

Answer 6

Если это домашнее задание, ваш учитель, вероятно, прося безобразно неэффективный ответ .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' 

Answer 7

спасибо всем за работу над этой проблемой. Мне также пришлось многому научиться из разных ответов. Вот как я ответил:

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)