Как найти уникальные элементы в двух списках

Задача: найти уникальные элементы в двух списках

Под уникальными элементами двух списков обычно понимают значения, которые встречаются только в одном из списков. Для этого удобно использовать множества и симметрическую разность ^; решение имеет среднюю временную сложность O(n + m).

Подробный ответ

Уточнение условия

Формулировка «уникальные элементы в двух списках» может означать разные вещи. В этом решении ищем элементы, которые есть только в первом или только во втором списке, но не присутствуют одновременно в обоих.

Решение через симметрическую разность

def unique_elements(first: list[int], second: list[int]) -> set[int]:
    return set(first) ^ set(second)

Пример

first = [1, 2, 3, 4]
second = [3, 4, 5, 6]

print(unique_elements(first, second))
# {1, 2, 5, 6}

Вариант через разность множеств

def unique_elements(first: list[int], second: list[int]) -> set[int]:
    first_set = set(first)
    second_set = set(second)

    return (first_set - second_set) | (second_set - first_set)

Если нужно сохранить порядок

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

def unique_elements_keep_order(first: list[int], second: list[int]) -> list[int]:
    first_set = set(first)
    second_set = set(second)
    result = []
    added = set()

    for value in first + second:
        if value not in first_set or value not in second_set:
            if value not in added:
                result.append(value)
                added.add(value)

    return result

Сложность

Построение двух множеств и симметрической разности занимает в среднем O(n + m), где n и m — размеры списков. Дополнительная память также равна O(n + m).

Как ответить на собеседовании

Сначала уточню, что под уникальными элементами понимаются элементы, присутствующие только в одном из списков. Затем использую симметрическую разность множеств: set(first) ^ set(second). Это решение работает в среднем за O(n + m), но не сохраняет порядок; если порядок важен, пройду по исходным спискам дополнительно.