350. Intersection of Two Arrays II

리트코드 350번 풀이

문제

Intersection of Two Arrays II

풀이

아이디어

349 - Intersection of Two Arrays 문제에서는 결과 요소들에 중복이 없어야 했지만, 이번에는 중복이 허용된다. 그래서 투포인터를 이용해서 풀기로 했다.

두 배열을 정렬한 뒤에, 각각의 포인터가 가리키는 요소가 같다면 결과 배열에 추가해줬다. 포인터는 값이 더 작은 쪽의 포인터를 증가시켜서 모든 요소를 비교할 수 있도록 했다.

투포인터를 풀기 전에 이 문제가 hash map 섹션으로 분류되어 있었던 만큼 Map을 이용해서 카운팅해주는 방법도 생각해봤는데, 투포인터를 이용하는 쪽이 좀 더 직관적인 것 같아서 투포인터 풀이로 결정했다. 하지만 투포인터의 경우에는 정렬에 걸리는 비용이 있기 때문에… 만약 시간복잡도를 더 중요하게 생각한다면 Map 풀이가 더 나을수도 있겠다.

코드

function intersect(nums1: number[], nums2: number[]): number[] {
  let ptr1 = 0,
    ptr2 = 0;
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  const ret: number[] = [];

  while (ptr1 < nums1.length && ptr2 < nums2.length) {
    if (nums1[ptr1] < nums2[ptr2]) ptr1++;
    else if (nums1[ptr1] > nums2[ptr2]) ptr2++;
    else {
      ret.push(nums1[ptr1]);
      (ptr1++, ptr2++);
    }
  }

  return ret;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n log n + m log m)
• 공간 복잡도: O(1)