Как найти дубликаты в списке Python с сохранением порядка элементов

Что значит «найти дубликаты с сохранением порядка»

В Python под поиском дубликатов могут подразумеваться разные результаты. Для списка [4, 2, 4, 3, 2, 4] возможны как минимум три варианта:

[4, 2] — каждое повторяющееся значение выводится один раз, в порядке обнаружения первого повтора;
[4, 2] — значения расположены по порядку их первого появления в исходном списке;
[4, 2, 4] — сохраняются все повторные вхождения, кроме первого появления каждого значения.

Для этого примера первые два результата совпадают, но так бывает не всегда. Например, для списка ["a", "b", "b", "a"] порядок первого повтора даст ["b", "a"], а порядок первого появления — ["a", "b"].

Уникальные дубликаты в порядке обнаружения повтора

Наиболее практичный вариант — пройти список один раз и использовать два множества:

seen хранит уже встреченные элементы;
added не позволяет добавить один и тот же дубликат несколько раз.

def find_duplicates(items):
    seen = set()
    added = set()
    duplicates = []

    for item in items:
        if item in seen and item not in added:
            duplicates.append(item)
            added.add(item)
        else:
            seen.add(item)

    return duplicates


values = [4, 2, 4, 3, 2, 4]
print(find_duplicates(values))
# [4, 2]

Порядок результата определяется моментом, когда значение встретилось второй раз. Значение 4 повторилось раньше значения 2, поэтому оно стоит первым.

Временная сложность такого решения в среднем составляет O(n), где n — длина списка. Дополнительная память также может достигать O(n).

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

Дубликаты в порядке первого появления

Иногда требуется сначала определить частоту значений, а затем пройти исходный список и выбрать элементы, встречающиеся более одного раза. Для подсчета удобно использовать collections.Counter.

from collections import Counter


def find_duplicates_by_first_position(items):
    counts = Counter(items)
    result = []
    added = set()

    for item in items:
        if counts[item] > 1 and item not in added:
            result.append(item)
            added.add(item)

    return result


values = ["a", "b", "b", "a"]
print(find_duplicates_by_first_position(values))
# ['a', 'b']

Здесь строка "a" попадает в результат первой, поскольку раньше появилась в исходном списке, хотя ее повтор обнаруживается позже повтора строки "b".

Этот способ также работает в среднем за O(n), но выполняет два логических прохода: сначала считает элементы, затем формирует результат.

Все повторные вхождения без первых экземпляров

Если нужно сохранить каждое повторение, достаточно одного множества. Первый экземпляр добавляется в seen, а все последующие отправляются в результат.

def find_repeated_occurrences(items):
    seen = set()
    repeated = []

    for item in items:
        if item in seen:
            repeated.append(item)
        else:
            seen.add(item)

    return repeated


values = [4, 2, 4, 3, 2, 4]
print(find_repeated_occurrences(values))
# [4, 2, 4]

Такой вариант полезен при анализе последовательности событий, идентификаторов или строк журнала, когда важно не только наличие дубликата, но и количество лишних вхождений.

Получение значений вместе с позициями повторов

При диагностике данных часто недостаточно узнать само значение. Полезно также получить индексы, на которых оно повторилось.

def find_duplicate_positions(items):
    first_positions = {}
    duplicates = []

    for index, item in enumerate(items):
        if item in first_positions:
            duplicates.append({
                "value": item,
                "first_index": first_positions[item],
                "duplicate_index": index,
            })
        else:
            first_positions[item] = index

    return duplicates


values = ["red", "blue", "red", "green", "blue"]

for duplicate in find_duplicate_positions(values):
    print(duplicate)

Результат:

{'value': 'red', 'first_index': 0, 'duplicate_index': 2}
{'value': 'blue', 'first_index': 1, 'duplicate_index': 4}

Функция сохраняет порядок повторных вхождений и показывает, где значение встретилось впервые. Если один элемент повторяется несколько раз, каждая дополнительная позиция будет выведена отдельно.

Генератор для больших последовательностей

Если список большой или данные поступают постепенно, необязательно сразу создавать полный список результата. Генератор возвращает дубликаты по одному.

def iter_duplicates(items):
    seen = set()
    yielded = set()

    for item in items:
        if item in seen:
            if item not in yielded:
                yielded.add(item)
                yield item
        else:
            seen.add(item)


values = [10, 20, 10, 30, 20, 40]

for duplicate in iter_duplicates(values):
    print(duplicate)

Генератор не хранит отдельный список найденных дубликатов, но множества seen и yielded все равно занимают память. Этот подход удобен, когда обработку результата можно начинать сразу, не дожидаясь завершения обхода входных данных.

Работа со списками и словарями

Элементы вроде [1, 2] или {"id": 5} являются нехешируемыми. Попытка добавить их в множество вызовет исключение TypeError.

values = [[1, 2], [3, 4], [1, 2]]

seen = set()
seen.add(values[0])
# TypeError: unhashable type: 'list'

Для вложенных списков можно преобразовать каждый элемент в кортеж:

def find_duplicate_lists(items):
    seen = set()
    added = set()
    duplicates = []

    for item in items:
        key = tuple(item)

        if key in seen and key not in added:
            duplicates.append(item)
            added.add(key)
        else:
            seen.add(key)

    return duplicates


values = [[1, 2], [3, 4], [1, 2], [1, 2]]
print(find_duplicate_lists(values))
# [[1, 2]]

Для словарей ключ можно построить из отсортированных пар:

def find_duplicate_dicts(items):
    seen = set()
    added = set()
    duplicates = []

    for item in items:
        key = tuple(sorted(item.items()))

        if key in seen and key not in added:
            duplicates.append(item)
            added.add(key)
        else:
            seen.add(key)

    return duplicates


values = [
    {"id": 1, "name": "Ann"},
    {"id": 2, "name": "Bob"},
    {"name": "Ann", "id": 1},
]

print(find_duplicate_dicts(values))
# [{'name': 'Ann', 'id': 1}]

Преобразование через tuple(sorted(item.items())) подходит только тогда, когда ключи и значения словаря можно корректно сравнивать и хешировать. Для вложенных словарей и списков потребуется рекурсивная нормализация данных.

Универсальный вариант с функцией ключа

В реальных задачах дубликаты часто определяются не по всему объекту, а по одному полю. Например, записи пользователей могут считаться одинаковыми по идентификатору.

def find_duplicates_by(items, key):
    seen = set()
    added = set()
    duplicates = []

    for item in items:
        marker = key(item)

        if marker in seen and marker not in added:
            duplicates.append(item)
            added.add(marker)
        else:
            seen.add(marker)

    return duplicates


users = [
    {"id": 10, "name": "Anna"},
    {"id": 20, "name": "Boris"},
    {"id": 10, "name": "Anna Updated"},
    {"id": 30, "name": "Chris"},
    {"id": 20, "name": "Boris Updated"},
]

duplicates = find_duplicates_by(users, key=lambda user: user["id"])

print(duplicates)
# [{'id': 10, 'name': 'Anna Updated'},
#  {'id': 20, 'name': 'Boris Updated'}]

В результат попадает объект, на котором соответствующий идентификатор повторился впервые. Порядок повторов сохраняется.

Короткая запись через списковое включение

Задачу можно записать компактно, но слишком короткие конструкции обычно хуже читаются. Один из допустимых вариантов для получения всех повторных вхождений:

seen = set()
values = [1, 2, 1, 3, 2, 1]

duplicates = [
    item
    for item in values
    if item in seen or not seen.add(item)
]

print(duplicates)
# [1, 2, 1]

Эту запись лучше не использовать. Метод set.add() возвращает None, а условие опирается на побочный эффект внутри спискового включения. Код работает неочевидно и усложняет сопровождение.

Более понятная функция с обычным циклом почти всегда предпочтительнее:

def find_repeated_occurrences(items):
    seen = set()
    result = []

    for item in items:
        if item in seen:
            result.append(item)
        else:
            seen.add(item)

    return result

Почему не стоит использовать count в цикле

Распространенная конструкция выглядит просто:

values = [1, 2, 1, 3, 2]

duplicates = []

for item in values:
    if values.count(item) > 1 and item not in duplicates:
        duplicates.append(item)

Метод list.count() каждый раз проходит по всему списку. Если вызвать его для каждого элемента, общая сложность может вырасти до O(n²). На небольших данных разница незаметна, но на десятках или сотнях тысяч элементов такой код становится существенно медленнее решения с множествами.

Дополнительная проверка item not in duplicates также выполняется линейно, поскольку duplicates является списком. Для контроля уникальности результата лучше использовать отдельное множество.

Сравнение основных вариантов

Задача	Подход	Порядок результата	Средняя сложность
Каждый дубликат один раз	Два множества	По первому повтору	`O(n)`
Повторяющиеся значения по первой позиции	`Counter` и множество	По первому появлению	`O(n)`
Все повторные вхождения	Одно множество	Как в исходном списке	`O(n)`
Дубликаты объектов по полю	Функция ключа и множества	По первому повтору ключа	`O(n)`
Проверка через `list.count()`	Повторные проходы списка	Зависит от реализации	`O(n²)`

Готовая функция для большинства задач

Для обычного списка хешируемых элементов подойдет следующая реализация:

def find_duplicates(items):
    """Возвращает уникальные дубликаты в порядке первого повтора."""
    seen = set()
    duplicates = []
    duplicate_keys = set()

    for item in items:
        if item in seen:
            if item not in duplicate_keys:
                duplicates.append(item)
                duplicate_keys.add(item)
        else:
            seen.add(item)

    return duplicates

Примеры проверки:

assert find_duplicates([]) == []
assert find_duplicates([1]) == []
assert find_duplicates([1, 1]) == [1]
assert find_duplicates([1, 2, 1, 2]) == [1, 2]
assert find_duplicates([1, 1, 1]) == [1]
assert find_duplicates(["b", "a", "a", "b"]) == ["a", "b"]

Итоговый чек-лист

Определите, нужен порядок первого появления или первого повторения.
Используйте set для хешируемых элементов и средней сложности O(n).
Применяйте два множества, если каждый дубликат должен попасть в результат только один раз.
Используйте одно множество, если нужны все повторные вхождения.
Применяйте Counter, когда важны частоты и порядок первого появления.
Для словарей и объектов формируйте хешируемый ключ или передавайте функцию key.
Не вызывайте list.count() внутри цикла на больших списках.
Добавьте проверки для пустого списка, списка без повторов и значения, повторенного несколько раз.