nlog(n) Python solution without Set


  • 0
    S

    Firstly,sort two arrays,using O(nlog(n))+O(mlog(m)),then use two pointer to compare values in the two arrays,if value in array1 < value in array2,then move pointer in array1 to next value which doesn't equal to pre value.

    class Solution(object):
        def intersection(self, nums1, nums2):
            result = []
            nums1.sort()
            nums2.sort()
            
            i, j = 0, 0
            len1, len2 = len(nums1), len(nums2)
            while i < len1 and j < len2:
                if nums1[i] < nums2[j]:
                    while i < len1 - 1 and nums1[i] == nums1[i+1]:
                        i += 1
                    i += 1
                elif nums1[i] == nums2[j]:
                    result.append(nums1[i]) # add to result
                    while i < len1 - 1 and nums1[i] == nums1[i+1]:
                        i += 1
                    i += 1
                    
                    while j < len2 - 1 and nums2[j] == nums2[j+1]:
                        j += 1
                    j += 1
                else:
                    while j < len2 - 1 and nums2[j] == nums2[j+1]:
                        j += 1
                    j += 1
                    
            return result
    

Log in to reply
 

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