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

Чтобы найти дубликаты в списке Python и сохранить порядок их первого повторного появления, проходите список слева направо, храните уже встреченные значения в одном set, а уже добавленные в результат дубликаты — во втором. Такой способ не сортирует исходные данные и не меняет список.

items = [4, 2, 7, 2, 4, 2, 9, 7]

seen = set()
added = set()
duplicates = []

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

print(duplicates)
# [2, 4, 7]

Результат [2, 4, 7] соответствует порядку, в котором значения впервые становятся дубликатами: второй экземпляр 2 встречается раньше второго экземпляра 4, затем повторяется 7.

Готовая функция

Для повторного использования вынесите алгоритм в функцию:

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

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

    return duplicates

Проверить функцию можно на нескольких входных данных:

print(find_duplicates([1, 3, 1, 2, 3]))
# [1, 3]

print(find_duplicates(["a", "b", "a", "c", "b"]))
# ['a', 'b']

print(find_duplicates([1, 2, 3]))
# []

print(find_duplicates([]))
# []

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

Как работает алгоритм пошагово

Рассмотрим список:

items = [5, 3, 5, 8, 3, 5]

Первое значение 5 еще не встречалось. Оно добавляется в seen.
Значение 3 тоже встречается впервые и добавляется в seen.
Следующее 5 уже находится в seen. Это дубликат, поэтому 5 добавляется в duplicates и одновременно в added.
Значение 8 встречается впервые и попадает только в seen.
Второе 3 найдено в seen, но отсутствует в added. Поэтому 3 добавляется в результат.
Последнее 5 уже есть и в seen, и в added. Повторно в результат оно не добавляется.

Итог:

[5, 3]

Почему недостаточно одного set

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

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

items = [1, 1, 1, 1]

seen = set()
duplicates = []

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

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

Если требуемый результат — [1], нужен второй набор added либо другая проверка уникальности результата.

Короткий вариант

Тот же алгоритм можно записать немного компактнее, не меняя его поведения:

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

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

    return duplicates

Здесь seen.add(x) вызывается на каждой итерации. Повторное добавление уже существующего элемента в множество не создает второй экземпляр.

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

Если элементы списка сами являются списками

Для вложенных списков следующий вариант работать не будет:

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

seen = set()

for item in items:
    seen.add(item)  # TypeError: list is unhashable

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

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)

        seen.add(key)

    return duplicates


items = [[1, 2], [3, 4], [1, 2], [5], [3, 4]]

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

Такое преобразование корректно только тогда, когда содержимое вложенного списка тоже подходит для создания хешируемого кортежа. Например, кортеж, содержащий обычный список, по-прежнему нельзя использовать как элемент set.

Универсальный вариант для нехешируемых значений

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

def find_duplicates_unhashable(items):
    seen = []
    duplicates = []

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

    return duplicates

Пример:

items = [
    {"id": 1},
    {"id": 2},
    {"id": 1},
    {"id": 3},
    {"id": 2},
]

print(find_duplicates_unhashable(items))
# [{'id': 1}, {'id': 2}]

Порядок сохраняется, но этот способ потенциально значительно медленнее метода с множествами: операция item in seen для списка выполняет последовательный поиск. При увеличении числа элементов количество сравнений может расти квадратично.

Если нужны все повторные вхождения

Иногда под «найти дубликаты» подразумевают не уникальные повторяющиеся значения, а каждое вхождение после первого. Тогда второй набор added не нужен:

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

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

    return duplicates


print(find_repeated_occurrences([2, 5, 2, 2, 5]))
# [2, 2, 5]

Здесь два последних экземпляра 2 считаются двумя отдельными повторными вхождениями.

Если нужны значения, встречающиеся больше одного раза

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

Разница видна на таком списке:

items = ["a", "b", "b", "a"]

Алгоритм из начала статьи возвращает ["b", "a"], потому что второе "b" встречается раньше второго "a". Если требуется ["a", "b"], сначала подсчитайте элементы, а затем еще раз пройдите исходный список.

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

def find_duplicates_by_first_appearance(items):
    counts = {}

    for item in items:
        counts[item] = counts.get(item, 0) + 1

    result = []
    added = set()

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

    return result


print(find_duplicates_by_first_appearance(
    ["a", "b", "b", "a"]
))
# ['a', 'b']

Здесь порядок результата определяется непосредственно вторым проходом по исходному списку. На порядок обхода самого словаря counts алгоритм не полагается.

Как выбрать вариант

Задача	Подход	Результат для `[2, 5, 2, 2, 5]`
Каждый дубликат один раз, по моменту первого повтора	`seen` + `added`	`[2, 5]`
Все вхождения после первого	Только `seen`	`[2, 2, 5]`
Дубликаты по порядку первого появления	Подсчет + второй проход	`[2, 5]`
Нехешируемые элементы	Сравнение через списки или собственный ключ	Зависит от данных

Сложность

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

Не следует обещать фиксированное время выполнения конкретного вызова: оно зависит от размера данных, типов объектов, их методов хеширования и сравнения, реализации Python и среды выполнения.

Вариант со списками для нехешируемых объектов использует последовательные проверки in. В худшем случае число сравнений растет как O(n²), поэтому для больших наборов данных лучше определить стабильный хешируемый ключ, если структура данных это позволяет.

Проверка результата

Минимальный набор проверок для функции, возвращающей каждый дубликат один раз:

assert find_duplicates([1, 2, 1]) == [1]
assert find_duplicates([1, 2, 1, 2]) == [1, 2]
assert find_duplicates([1, 1, 1]) == [1]
assert find_duplicates([1, 2, 3]) == []
assert find_duplicates([]) == []
assert find_duplicates(["x", "y", "x"]) == ["x"]

Если эти выражения выполняются без AssertionError, функция возвращает ожидаемые результаты именно для перечисленных тестовых случаев. Это не доказывает корректность для любых возможных пользовательских типов объектов, особенно если они имеют нестандартные реализации сравнения или хеширования.

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

Нужно сохранить порядок обнаружения повторов — проходите исходный список слева направо.
Нужно вернуть каждый дубликат один раз — используйте seen и added.
Нужны все повторные вхождения — достаточно seen.
Нужен порядок первого появления значений — подсчитайте частоты и выполните второй проход по исходному списку.
Перед использованием set убедитесь, что элементы хешируемые.
Для списков и словарей определите хешируемый ключ либо используйте сравнение без множества.
Не применяйте сортировку, если необходимо сохранить исходный порядок.
Проверяйте отдельно пустой список, отсутствие повторов, многократные повторы и реальные типы данных приложения.