[LeetCode] Intersection of Two Arrays

1번. 이진 검색

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = set()
        nums2.sort()
        for num in nums1:
            idx = bisect.bisect_left(nums2, num)
            if idx < len(nums2) and nums2[idx] == num:
                result.add(num)
        
        return result    

O(nlogn)
nums1을 순차적으로 O(n), nums2에서 검색 O(logn)

• bisect는 정렬된 배열에서 삽입될 위치를 찾아주는 것.

2번. 투 포인터

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()

        nums1.sort()
        nums2.sort()
        i, j = 0, 0

        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                result.add(nums1[i])
                i += 1
                j += 1
        return result

O(nlogn)
nums1, nums2 정렬에 2 * O(nlogn), 반복문 비교 O(2n)
정렬을 제외한 비교의 시간 복잡도는 O(n)에 불과

• 각 배열에 포인터를 하나씩 다음으로 이동하다가 하나의 배열 끝까지 비교하면 멈춤