Intersection of Two Arrays

Возьмите каждое значение из nums1 и ищите его в nums2. Остановите поиск при первом совпадении и пропустите значение, которое уже есть в ответе, поэтому для [8, 8, 8, 8] и [8, 8] результатом будет одна 8, а не четыре. В конце отсортируйте ответ.

Это правильно, потому что значение попадает в ответ, только если какая-либо его копия в nums1 находит совпадение в nums2, а пропуск не позволяет добавить его дважды.

Это медленно, потому что для каждого значения из nums1 может выполняться поиск по всему nums2. Если в каждом массиве по 5000 значений, это до 2.5 × 10^7 сравнений, а в больших тестах большинство значений не находит совпадений, поэтому большинство поисков доходит до конца.

После сортировки пример 1 превращается в [2, 2, 4, 6, 9] и [1, 4, 4, 6]. Поставьте указатель i в начало первого массива, а j — в начало второго. Указатель на меньшее значение сдвигается вперёд: это значение не может совпасть ни с одним из дальнейших значений другого массива, где все значения не меньше него. Когда оба указателя указывают на одно и то же значение, оно есть в обоих массивах, поэтому добавьте его и сдвиньте оба указателя.

Рассмотрим пример: 2 > 1 сдвигает j, оба значения 2 меньше 4, поэтому сдвигается i, 4 = 4 — добавляем 4, второе значение 4 меньше 6, поэтому сдвигается j, а 6 = 6 — добавляем 6. Значение, встречающееся несколько раз в обоих массивах, например 2 в [2, 2, 3] и [2, 2], совпадает больше одного раза; сравнение с последним добавленным значением позволяет оставить только одну копию. Результат сразу получается отсортированным, без дополнительных шагов.

Сортировка требует O(n log n + m log m), а проход — O(n + m), поскольку на каждом шаге сдвигается как минимум один указатель. В большинстве вариантов сортируются копии массивов, что требует O(n + m) дополнительной памяти. Если входные данные можно переупорядочить, отсортируйте массивы на месте, как это делает код на C, — тогда единственная дополнительная память понадобится для ответа.

Помести каждое значение из nums1 в хеш-множество. В примере 1 множество выглядит так: {6, 2, 9, 4}: повторяющаяся 2 схлопывается при добавлении. Затем пройди по nums2 и проверь каждое значение в множестве за константное время. Первая 4 там есть, поэтому она попадает в ответ. Вторая 4 попасть туда не должна, поэтому удаляй значение из множества сразу после совпадения. 1 там нет, а 6 есть, что дает [4, 6].

Удаление при совпадении позволяет сохранить каждое значение только один раз: после первого совпадения значение исчезает из множества, поэтому более поздние копии в nums2 ничего не находят. Каждое добавленное значение есть в обоих массивах, и каждое общее значение добавляется при появлении его первой копии в nums2.

Построение множества и проход занимают в среднем O(n + m). Ответ получается в порядке элементов nums2, поэтому в конце отсортируй его; в нем содержится k ≤ min(n, m) значений, что требует O(k log k). В C нет встроенного множества, поэтому в коде на C используется массив флагов с индексами value + 10^5, что работает, поскольку значения ограничены.