3 easy-to-understand solutions in Python


  • 0
    T
        **"""nested loop, Time Complexity O(n^2)"""**
        if not nums1 or not nums2: 
            return []
        res =[]
        for x in nums1:
            for y in nums2:
                if x == y:
                    if x not in res:
                        res.append(x)
        return res
    
        **"""Binary Search,  Time Complexity O(nlogn)"""**
        nums1 = list(set(nums1))
        nums1.sort()
        L = len(nums1)
        res = set()
        for x in nums2: 
            l, r = 0, L-1
    
            while l <= r:
                m = (r + l) / 2
                if x > nums1[m]:
                    l = m + 1
                elif x < nums1[m]:
                    r = m - 1
                else: 
                    res.add(x)
                    break
            
        return list(res)
    
        **"""Hash Set, Time Complexity O(n)"""**
        hashed_nums1 = set(nums1)
        res = set()
        for x in nums2: 
            if x in hashed_nums1: 
                res.add(x)
        return list(res)

Log in to reply
 

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