[LeetCode] 350. Intersection of Two Arrays II | LIM

문제

https://leetcode.com/problems/intersection-of-two-arrays-ii/

Intersection of Two Arrays II - LeetCode

 

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

 

Example1

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

 

Example2

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

 

설명

두 array에서 공통 원소 구한 후 array로 return 하기

 

푼 방식

1. nums2 배열에서 원소를 하나씩 pop 한다. (pop(0))

2. nums1 배열을 정렬한 다음 binary_search 로 1번에서 뽑은 원소가 있는지 탐색한다.

3-1. 만약 있을 경우 return 할 리스트에 append 하고, 해당하는 원소를 nums1 배열에서 제거한다.

3-2. 만약 없을 경우 1번으로 돌아간다.

 

코드

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        while nums2:
            nums1_sorted = sorted(nums1)
            selected = nums2.pop(0)
            result = self.binary_search(selected, nums1_sorted)
            if result is not None:
                ans.append(nums1_sorted[result])
                nums1_sorted.pop(result)
                nums1 = nums1_sorted
        return ans


    def binary_search(self, target, data):
        # 인덱스 설정
        start = 0
        end = len(data) - 1

        while start <= end:
            mid = (start + end) // 2
            if data[mid] == target:
                return mid
            elif data[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return None

 

결과

 

---

다른방식(Two Pointer 이용하기)

Two Pointer 방식을 이용해서 푸는 방식

 

1. nums1과 nums2를 정렬한다.

2. nums1과 nums2에 pointer를 하나씩 설정해 두고 값을 비교한다.

3-1. 값이 같은 경우 return 할 리스트에 값을 append 한다.

3-2. nums1의 인덱스 값이 nums2의 인덱스 값보다 클 경우 nums2의 인덱스 값을 한 칸 늘린다.

3-3. nums2의 인덱스 값이 nums1의 인덱스 값보다 클 경우 nums1의 인덱스 값을 한 칸 늘린다.

4. nums1의 pointer 혹은 nums2의 pointer 가 끝까지 가면 종료한다.

 

코드

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        nums1.sort()
        nums2.sort()
        i, j = 0, 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                ans.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] >  nums2[j]:
                j += 1
            else:
                i += 1
        return ans

 

결과

 

Runtime 이 첫 번째 푼 방법보다 훨씬 개선되었다!