[Leetcode]349. Intersection of Two Arrays

📄 Description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

두 배열의 교집합을 구하라.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

💻 My Submission - Using Two Pointers

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        p1=p2=0
        answer: Set=set()
        
        while p1<len(nums1) and p2<len(nums2):
            if nums1[p1]<nums2[p2]: p1+=1
            elif nums1[p1]>nums2[p2]: p2+=1
            else:
                answer.add(nums1[p1])
                p1+=1
                p2+=1
        return answer

🔨 My Solution

• 값이 작은 쪽 배열의 포인터가 한 칸씩 앞으로 이동하는 형태
• 어느 한쪽의 포인터가 끝까지 도달하면 종료

🕐 Complexity

Time Complexity: O(nlogn)

• 정렬: 2*O(nlogn)
• 비교: O(2n)
  정렬을 제외하면, 비교에 따른 시간 복잡도는 상수항을 제외해서 O(n)에 불과하다.

💭 Another Approach - Binary Search

한쪽은 순서대로 탐색, 다른 쪽은 정렬해서 이진 검색으로 값을 찾는다.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums2.sort()
        
        answer: Set=set()
        
        # nums2에서 이진탐색
		for n1 in nums1:
        	i2 = bisect.bisect_left(nums2, n1)
            if len(nums)>0 and i2<len(nums2) and n1==nums2[i2]:
            	answer.add(n1)
        return answer

🕐 Complexity

Time Complexity: O(nlogn)

• nums2는 정렬된 상태에서, nums을 $O(n)$ 순차 반복하면서 nums2를 $O(log n)$ 이진 검색한다.

References

• https://leetcode.com/problems/intersection-of-two-arrays/
• 파이썬 알고리즘 인터뷰(95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트), 박상길 지음