Пересечение двух списков

Пересечение двух списков

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

Решение 1: Использование множеств

def intersection(list1, list2):
    """Найти пересечение двух списков через множества."""
    return list(set(list1) & set(list2))

# Примеры
print(intersection([1, 2, 3, 4], [3, 4, 5, 6]))  # [3, 4]
print(intersection([1, 2], [3, 4]))               # []
print(intersection([1, 1, 2, 2], [1, 2, 2, 3]))  # [1, 2]

Решение 2: Сохранение порядка (list comprehension)

def intersection_v2(list1, list2):
    """Найти пересечение, сохраняя порядок из list1."""
    set2 = set(list2)
    return [x for x in list1 if x in set2]

# Примеры
print(intersection_v2([1, 2, 3, 4], [3, 4, 5, 6]))  # [1, 2, 3, 4]
print(intersection_v2([4, 3, 2, 1], [3, 4, 5, 6]))  # [4, 3]
print(intersection_v2([1, 2], [3, 4]))               # []

Решение 3: Без дубликатов в результате

def intersection_v3(list1, list2):
    """Найти пересечение без дубликатов, сохраняя порядок."""
    set2 = set(list2)
    result = []
    seen = set()
    
    for x in list1:
        if x in set2 and x not in seen:
            result.append(x)
            seen.add(x)
    
    return result

# Примеры
print(intersection_v3([1, 1, 2, 2], [1, 2, 2, 3]))  # [1, 2]
print(intersection_v3([1, 2, 3, 3, 4], [2, 3, 3, 5]))  # [2, 3]

Решение 4: Двойной цикл (без дополнительной памяти)

def intersection_v4(list1, list2):
    """Найти пересечение через вложенные циклы."""
    result = []
    for x in list1:
        if x in list2:
            result.append(x)
    
    return list(set(result))  # Удаляем дубликаты

# Примеры
print(intersection_v4([1, 2, 3, 4], [3, 4, 5, 6]))  # [3, 4]
print(intersection_v4([1, 1, 2, 2], [1, 2, 2, 3]))  # [1, 2]

Решение 5: Встроенный метод (если списки — это множества)

def intersection_v5(list1, list2):
    """Использование встроенного метода множеств."""
    return list(set(list1).intersection(set(list2)))

# Эквивалентно первому решению
print(intersection_v5([1, 2, 3, 4], [3, 4, 5, 6]))  # [3, 4]

Сравнение подходов

import timeit

list1 = list(range(10000))
list2 = list(range(5000, 15000))

# Способ 1: set() & set()
time1 = timeit.timeit(
    lambda: list(set(list1) & set(list2)),
    number=1000
)

# Способ 2: list comprehension с set
time2 = timeit.timeit(
    lambda: [x for x in list1 if x in set(list2)],
    number=1000
)

# Способ 3: double loop + set
time3 = timeit.timeit(
    lambda: list(set([x for x in list1 if x in list2])),
    number=1000
)

print(f"set() & set(): {time1:.4f} сек")
print(f"list comprehension: {time2:.4f} сек")
print(f"double loop: {time3:.4f} сек")
print("\nВывод: Использование множеств & множества — наиболее эффективно")

Обработка граничных случаев

def test_intersection():
    test_cases = [
        ([1, 2, 3, 4], [3, 4, 5, 6], [3, 4]),
        ([1, 2], [3, 4], []),
        ([], [1, 2, 3], []),
        ([1, 2, 3], [], []),
        ([], [], []),
        ([1, 1, 2, 2], [1, 2, 2, 3], [1, 2]),
        ([1], [1], [1]),
        ([1], [2], []),
        ([1, 2, 3], [1, 2, 3], [1, 2, 3]),
    ]
    
    for list1, list2, expected_set in test_cases:
        result = list(set(list1) & set(list2))
        result_set = set(result)
        expected_set = set(expected_set)
        
        assert result_set == expected_set, f"Ошибка: intersection({list1}, {list2}) = {result}, ожидается {list(expected_set)}"
        print(f"✓ intersection({list1}, {list2}) = {sorted(result)}")
    
    print("\nВсе тесты пройдены!")

test_intersection()

Продвинутые варианты

Пересечение множества списков

def intersection_multiple(*lists):
    """Найти пересечение нескольких списков."""
    if not lists:
        return []
    
    result = set(lists[0])
    for lst in lists[1:]:
        result &= set(lst)
    
    return list(result)

# Примеры
print(intersection_multiple([1, 2, 3], [2, 3, 4], [2, 3, 5]))  # [2, 3]
print(intersection_multiple([1, 2, 3]))  # [1, 2, 3]
print(intersection_multiple())  # []

С сохранением дубликатов

from collections import Counter

def intersection_with_duplicates(list1, list2):
    """Найти пересечение с учётом количества дубликатов."""
    count1 = Counter(list1)
    count2 = Counter(list2)
    
    result = []
    for elem in count1:
        if elem in count2:
            result.extend([elem] * min(count1[elem], count2[elem]))
    
    return result

# Примеры
print(intersection_with_duplicates([1, 1, 2, 2], [1, 2, 2, 3]))  # [1, 2, 2]
print(intersection_with_duplicates([1, 1, 1], [1, 1]))           # [1, 1]

Пересечение отсортированных массивов

def intersection_sorted(list1, list2):
    """Оптимизированное пересечение для отсортированных списков."""
    result = []
    i, j = 0, 0
    
    while i < len(list1) and j < len(list2):
        if list1[i] == list2[j]:
            result.append(list1[i])
            i += 1
            j += 1
        elif list1[i] < list2[j]:
            i += 1
        else:
            j += 1
    
    return result

# Примеры (массивы должны быть отсортированы)
print(intersection_sorted([1, 2, 3, 4], [2, 3, 4, 5]))  # [2, 3, 4]
print(intersection_sorted([1], [1]))                    # [1]

Анализ сложности

"""
Метод 1: set() & set()
  - Временная сложность: O(n + m) где n и m — размеры списков
  - Пространственная сложность: O(min(n, m))
  - Быстро, хорошо работает на больших данных

Метод 2: list comprehension с set
  - Временная сложность: O(n) где n — размер первого списка
  - Пространственная сложность: O(m) для множества
  - Сохраняет порядок из первого списка

Метод 3: двойной цикл
  - Временная сложность: O(n * m) — могла быть O(n) с оптимизацией
  - Пространственная сложность: O(1) дополнительно
  - Медленнее на больших данных

Метод 4: отсортированные массивы
  - Временная сложность: O(n + m)
  - Пространственная сложность: O(1) если не считать результат
  - Только если массивы уже отсортированы
"""

Рекомендации

1. Для большинства случаев: используйте set() & set() или set(list1).intersection(set(list2))
2. Если важен порядок: используйте list comprehension с set2
3. Для учебных целей: рассмотрите двойной цикл (O(n*m))
4. Для больших отсортированных данных: используйте двухточечный метод

# Финальное рекомендуемое решение
def intersection(list1, list2):
    """Найти пересечение двух списков."""
    return list(set(list1) & set(list2))

# Или с сохранением порядка
def intersection_ordered(list1, list2):
    """Найти пересечение, сохраняя порядок из list1."""
    set2 = set(list2)
    return [x for x in list1 if x in set2]