Given two arrays, write a function to compute their intersection.

Notice

• Each element in the result must be unique.
• The result can be in any order.

Have you met this question in a real interview?

Yes

Example

Givennums1=[1, 2, 2, 1],nums2=[2, 2], return[2].

(should be able to be solved using three different method, please see, two pointer)

binary search on the smaller array(so, sort the smaller array, and do the look up on the larger array)

O(nlogm + mlogm)

O(mlogn + nlogn)

O((m + n) * logn)

O((m + n) * logm)

because the above induction

 #binary search
    def intersection(self, nums1, nums2):
        # write your code here
        def binary_search(nums, target):
            start = 0
            end = len(nums) - 1

            while start + 1 < end:
                mid = (start + end) // 2
                if nums[mid] == target:
                    return True
                if nums[mid] < target:
                    start = mid
                else:
                    end = mid

            if nums[start] == target or nums[end] == target:
                return True
            return False

        def get_insersection(nums_target, nums_source):
            ans = set()
            for num in nums_source:
                if num in ans:
                    continue
                elif binary_search(nums_target, num):
                    ans.add(num)
            return list(ans)

        if not nums1 or not nums2:
            return []

        if len(nums1) < len(nums2):
            nums2.sort()
            return get_insersection(nums2, nums1)

        nums1.sort()
        return get_insersection(nums1, nums2)