Easy python solution with binary search.


  • 0
    A
    class Solution:
        def binarySearch(self, nums, key):
            lowerBound = 0
            upperBound = len(nums) - 1
            while (True):
                # not found
                if (lowerBound > upperBound):
                    return False
                # avoid overflow.
                mid = lowerBound + (upperBound - lowerBound) // 2
                if (nums[mid] == key):
                    return True
                if (nums[mid] < key):
                    lowerBound = mid + 1
                else:
                    upperBound = mid - 1
                
        def intersection(self, nums1, nums2):
            result = []
            # sort nums2 before using binarySearch
            nums2.sort()
            for digit in nums1:
                if self.binarySearch(nums2, digit) and digit not in result:
                    result.append(digit)
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.