[Leetcode]349. Intersection of Two Arrays

limelimejiwon·2022년 4월 13일
0

📄 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)에 불과하다.

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

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는 정렬된 상태에서, numsO(n)O(n) 순차 반복하면서 nums2O(logn)O(log n) 이진 검색한다.

References

profile
Make your lives Extraordinary!

0개의 댓글