Легкий
Проблема
Имея два массива, напишите функцию для вычисления их пересечения.
Пример 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
Пример 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9]
Примечание.
- Каждый элемент в результате должен появляться столько раз, сколько он отображается в обоих массивах.
- Результат может быть в любом порядке.
Последующие действия:
- Что делать, если данный массив уже отсортирован? Как бы вы оптимизировали свой алгоритм?
- Что, если размер nums1 меньше размера nums2? Какой алгоритм лучше?
- Что делать, если элементы nums2 хранятся на диске, а память ограничена так, что вы не можете загрузить все элементы в память сразу?
Решение — хеш-карта
Используйте хэш-карту, чтобы сохранить количество всех чисел в nums1
и проверить каждое число в nums2
.
Сложность
Без ограничения общности предположим, что m
и n
обозначают количество чисел в nums1
и nums2
. Во-первых, для построения хэш-карты требуется O(m) времени. Затем требуется n
проверка для фильтрации каждого элемента в nums2
. Для каждой проверки требуется время O(1)/O(logm) для поиска и обновления в хэш-карте в среднем/худшем случае. Следовательно, его временная сложность будет O(m + n)/O(m + nlogm) в среднем/худшем случае.
Из-за сложности пространства он использует O(m) дополнительного пространства для хранения хэш-карты.
Решение — два указателя
Сначала отсортируйте оба списка, затем мы сможем решить эту проблему, используя два указателя.
Сложность
Сортировка обоих списков занимает время O(mlogm + nlogn), если m
и n
обозначают количество чисел nums1
и nums2
. Затем для отслеживания двух указателей требуется время O (m + n). Поэтому его временная сложность будет O(mlogm + nlogn + m + n) = O(mlogm + nlogn).
Тривиально, что он использует только O(1) дополнительного пространства.
Следовать за
Что делать, если данный массив уже отсортирован? Как бы вы оптимизировали свой алгоритм?
Временная сложность подхода с двумя указателями будет O(m + n).
Что, если размер nums1 меньше размера nums2? Какой алгоритм лучше?
Для подхода с хэш-картой его временная сложность будет O(m + n)/O(m + nlogm) = O(n)/O(nlogm) с дополнительным пространством O(m) в среднем/худшем дела. Для подхода с двумя указателями его временная сложность будет O(mlogm + nlogn) = O(nlogn) с дополнительным пространством O(1).
Таким образом, подход с хэш-картой будет стоить меньше времени, но подход с двумя указателями будет стоить меньше места.
Что делать, если элементы nums2 хранятся на диске, а память ограничена так, что вы не можете загрузить все элементы в память сразу?
В данном случае это означает, что n
намного больше, чем m
, а это значит, что мы должны максимально уменьшить n
. Следовательно, будет лучше использовать подход хэш-карты, потому что его временная сложность составляет только O (n).