[LeetCode] 349. Intersection of Two Arrays

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

두 배열의 교집합을 구하세요.

✍️ 풀이

---

1. 브루트포스하게 풀며 set를 추가로 이용한 방법 O(n^2)
2. 배열하나를 정렬하고 나머지 한 배열을 반복하면서 정렬된 배열에서 값을 이진탐색을 찾는 방법 O(nlogn)
3. 투 포인터로 찾는 방법 -> 정렬 + 투 포인터 탐색 O(nlogn)

🛠 코드

---

• 2번 방법 코드
  • bisect로 얻은 i2는 범위 검사를 꼭 해줘야 한다.

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

---

📝 정리

---

🎈 참고

---

Book 링크