Легкий

Проблема

Имея два массива, напишите функцию для вычисления их пересечения.

Пример 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).