Python вернуть список дубликатов в списке по порядку - PullRequest
Новая
       22

Python вернуть список дубликатов в списке по порядку

0 голосов
/ 10 апреля 2020

Как быстро вернуть список дубликатов для списка в порядке их появления? Например, duplicates([2,3,5,5,5,6,6,3]) results in [5,6,3] означает, что повторяющийся элемент добавляется в результирующий список дубликатов только тогда, когда появляется его второй элемент. Пока у меня есть код ниже, но он не работает достаточно быстро, чтобы пройти большие тестовые случаи. Есть ли более быстрый вариант без импорта? 

def duplicates(L):
    first = set()
    second = []
    for i in L:
        if i in first and i not in second:
            second.append(i)
            continue
        if i not in first and i not in second:
            first.add(i)
            continue
    return second

Ответы [ 2 ]

0 голосов
/ 10 апреля 2020

Вы преуспели в использовании набора first, поскольку он имеет временную сложность O (1) для операции in. Но с другой стороны, вы используете список для second, который превращает эту функцию в O (N ^ 2) и, в худшем случае, вы дважды просматриваете список second.

Итак, я рекомендую вам использовать словарь для хранения найденных вами чисел.

Например: 

def duplicates(L):
    first = dict()
    second=[]
    for i in L:
        if i not in first:      #First time the number appears
            first[i] = False
        elif not first[i]:      #Number not on the second list
            second.append(i)
            first[i]=True

return second

Обратите внимание, что я использовал логическое значение для значения ключа словаря для представляет, появляется ли число более 1 раза или нет (или оно уже было добавлено в список de second). Это решение имеет O (N) временную сложность, что означает, что это намного быстрее.

0 голосов
/ 10 апреля 2020

Редакция размещенного кода

  • Использовать словарь, а не список для 'second' в коде OP.
  • Список Dicts имеет O (1), а не O (n) время поиска
  • Dicts отслеживают порядок вставки для Python 3.6+ или могут использовать OrderedDict

Код 

def duplicatesnew(L):
    first = set()
    second = {}   # Change to dictionary
    for i in L:
        if i in first and i not in second:
            second[i] = None
            continue
        if i not in first and i not in second:
            first.add(i)
            continue

    return list(second.keys())  # report list of keys

    lst = [2,3,5,5,5,6,6,3]

Производительность

Сводка

  • Сравнимо в коротких списках
  • В 2 раза быстрее в длинных списках

Тесты

Использовать списки длины N

Для N = 6: использовать исходный список

N> 6 использовать: 

lst = [random.randint(1, 10) for _ in range(N)]

  1. N = 6

    Оригинал: 2.24 us Пересмотрено: 2.74 us

  2. 1000 случайных чисел от 1 до 10

    Оригинал: 241 us Пересмотрено: 146 us

  3. N = 100, 000

    Оригинал: 27,2 мс Пересмотрено: 13,4 мс

...