Хеш-таблицы

Пересечение двух массивов

Найти общие элементы двух массивов

Легкий

Постановка задачи

Описание (LeetCode)

Даны два целочисленных массива nums1 и nums2, верните массив с элементами их пересечения. Каждый элемент в результате должен быть уникальным, а вернуть результат можно в любом порядке.

Пример 1:

nums1 = [1, 2, 2, 1], nums2 = [2, 2]

Результат:

[2]

Пояснение:

Число 2 присутствует как в первом, так и во втором массиве.

Пример 2:

nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]

Результат:

[9, 4] или [4, 9]

Пояснение:

В пересечении есть только два числа: 4 и 9.

Ограничения:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 1000

Решение

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

Вот несколько примеров, где нужно уметь эффективно находить пересечения двух множеств:

Рекомендательные системы: если интересы двух покупателей пересекаются, можно рекомендовать им похожие вещи.
Поиск по тегам: нужно найти список документов для каждого тега, а затем вычислить их пересечение, чтобы показать документы, помеченные всеми тегами.
Базы данных: операция INTERSECT - это буквально реализация этой задачи. Операция ищет пересечение множеств, возвращая только те данные, которые присутствуют в результатах обоих запросов.

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

Эффективное решение этой задачи достаточно простое. Вместо полного перебора мы будем использовать хеш-множества.

Идея решения:

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

Основные шаги:

Заполняем первое множество: создаем nums1Set и добавляем в него все элементы из первого массива nums1. Так мы автоматически уберем все дубликаты из первого массива. Теперь поиск любого числа в nums1Set будет занимать константное время O(1).
Инициализируем результат: создаем пустое хеш-множество nums2Set. Мы используем nums2Set, чтобы избежать повторов в результате, если во втором массиве одно и то же число встретится несколько раз.
Поиск совпадений: проходим по второму массиву nums2 и для каждого числа:
- Проверяем, есть ли это число в nums1Set.
- Если да, то добавляем его в nums2Set.
Получение результата: после завершения цикла преобразуем nums2Set в массив и вернем его.

Рассмотрим это подробнее на примере nums1 = [1, 2, 2, 1], nums2 = [2, 2].

Создаем множество из первого массива

Мы берем nums1 и добавляем каждый его элемент в nums1Set.
Берем 1, затем 2. Повторные 2 и 1 игнорируются.
Результат: nums1Set = {1, 2}.

Инициализируем результат
- Подготавливаем пустое множество для ответа nums2Set = {}. Оно нужно, чтобы складывать туда найденные элементы пересечения.
Поиск совпадений
- Мы берем элементы из nums2 = [2, 2] по очереди и проверяем, есть ли они в nums1Set.
- Число 2 есть в nums1Set? Да, добавляем в nums2Set, nums2Set = {2}.
- Следующее число 2 есть в nums1Set? Да, пытаемся добавить в nums2Set, но так как это хеш-множество и 2 там уже есть, результат не изменится: nums2Set = {2}.
Получение результата
- Преобразуем nums2Set в массив.

Итог: [2]

Почему это эффективно?

Эффективность этого подхода с использованием хеш-множеств строится на скорости поиска O(1) в хеш-множествах и линейном проходе по двум массивам.

Оценка сложности

Временная сложность

Мы сначала делаем один проход по nums1 и добавляем элементы в nums1Set. Это линейная сложность: O(n), где n - количество элементов в nums1, так как добавление элемента в хеш-множество nums1Set занимает O(1) в среднем.

Затем делаем проход по массиву nums2 и добавляем элементы в nums2Set. Это тоже линейная сложность: O(m), где m - количество элементов в nums2.

И наконец, преобразуем nums2Set в массив за O(k), где k - количество уникальных элементов в ответе.

Таким образом общая временная сложность: O(n + m + k).

Пространственная сложность

Мы используем два дополнительных хеш-множества: nums1Set и nums2Set. Первое может хранить до n уникальных элементов из nums1, а второе - до k элементов ответа. Поэтому пространственная сложность равна O(n + k), где k - количество уникальных элементов в пересечении двух массивов.

Интервьюер может задать дополнительный вопрос: "А как еще решить эту задачу, если мы ограничены по памяти и нельзя использовать хеш-множества?"

Ответ:

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

Сложность такого решения будет O(n * log n + m * log m) из-за сортировки, но мы не будем использовать дополнительную память для хеш-множеств.

Код решения

Приведем код решения.

func intersection(nums1 []int, nums2 []int) []int {
    nums1Set := map[int]struct{}{}
    for _, v := range nums1 {
        nums1Set[v] = struct{}{}
    }
 
    nums2Set := map[int]struct{}{}
    for _, v := range nums2 {
        if _, ok := nums1Set[v]; ok {
            nums2Set[v] = struct{}{}
        }
    }
 
    result := []int{}
    for k, _ := range nums2Set {
        result = append(result, k)
    }
    return result
 
}

В некоторых языках код решения может быть значительно короче, например в Python это может выглядеть вот так:

def intersection(nums1, nums2):
    return list(set(nums1) & set(nums2))

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

Интервьюер хочет видеть ваше алгоритмическое мышление, а не знание синтаксиса Python. Если вы сразу выдали однострочное решение set(nums1) & set(nums2), то это скроет важные моменты:

понимаете ли вы, как работает хеш-таблица под капотом?
знаете ли, какая у этого решения временная сложность?
умеете ли обрабатывать условия уникальности?

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

Итоги

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

У этой задачи есть дополнение, которое мы рекомендуем вам решить самостоятельно - Intersection of Two Arrays II (Подсказка: вместо хеш-множества используйте хеш-таблицу и храните пару "число: сколько раз оно встретилось".)

Подведем итоги по этой задаче:

Уникальность элементов. Нам надо найти уникальные общие элементы двух массивов. Даже если число повторяется в обоих массивах многократно, в итоговый список оно попадает один раз.
Основная идея. Использование хеш-множеств дает нам очень эффективный способ нахождения пересечения двух массивов.
Эффективность. Поиск в хеш-множестве занимает в среднем O(1). Мы проходим по каждому массиву ровно один раз, поэтому итоговая сложность равна O(n + m + k).
Практическое значение. Это фундаментальный алгоритм, который используется везде: от поисковых фильтров в интернет-магазинах до систем сопоставления данных.