1 minute read

349. Intersection of Two Arrays

문제 링크

https://leetcode.com/problems/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.

제한 사항

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

입출력 예 #1

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

입출력 예 #2

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

문제 풀이

  1. 브루트 포스로 계산
  2. 이진 검색으로 일치 여부 판별
  3. 투 포인터로 일치 여부 판별
  4. 파이썬 다운 해결 방법
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        for num in set(nums2) :
            if num in nums1 :
                result.append(num)
        return result

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()
        nums2.sort()
        for n1 in nums1:
            # 이진 검색으로 일치 여부 판별
            i2 = bisect.bisect_left(nums2, n1)
            if len(nums2) > 0 and len(nums2) > i2 and n1 == nums2[i2]:
                result.add(n1)
        return result

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result: Set = set()
        # 양쪽 모두 정렬
        nums1.sort()
        nums2.sort()
        i = j = 0
        # 투 포인터 우측으로 이동하며 일치 여부 판별
        while i < len(nums1) and j < len(nums2):
            if nums1[i] > nums2[j]:
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                result.add(nums1[i])
                i += 1
                j += 1

        return result

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return {*nums1} & {*nums2}

Comments

You May Also Enjoy