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, 3]과 [2, 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를 인덱스로 사용하는 플래그 배열을 씁니다. 값의 범위가 제한되어 있기 때문에 이 방법을 사용할 수 있습니다.