349. Intersection of Two Arrays.md

349. Intersection of Two Arrays (Easy)

[tag] set, binary search two pointers

Method 1. 2 set

• time: O(m+n) space: O(m+n)

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        i = j = 0
        ans = []
        nums1_set = set(nums1)
        nums2_set = set(nums2)
        for num in nums2_set:
            if num in nums1_set:
                ans.append(num)
        return ans
      # return list(set2 & set1)

Method 2. Binary search

from bisect import bisect_left
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = set()
        nums1.sort()
        for num in nums2:
            if(self.binary_search(nums1, num) != -1):
                ans.add(num)
        return ans 

    def binary_search(self, a, x):
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return i
        else:
            return -1