Two Python solutions

  • 1

    First solution: not sure about the time complexity, anyone knows the complexity of dict.has_key?

    Or we can choose the shorter array to do the search, which can save some time. This also answers the follow-up question #2.

    Second solution, sort(). 52ms too. Of course, if the array is pre sorted, second solution saves a lot of time. This answers the follow-up question #1.

    About the follow-up questions #3, solution 1 works well. We can save nums1 first, and check each element in nums2.

    solution 1: using dict 52ms

        def intersect(self, nums1, nums2):
            import collections
            dict1 = dict(collections.Counter(nums1))
            res = []
            for i in nums2:
                if dict1.has_key(i):
                    if dict1[i] > 0:
                        dict1[i] -= 1
            return res

    solution 2: sort() 52ms

        def intersect(self, nums1, nums2):
            res = []
            i, j = 0, 0
            while i < len(nums1) and j < len(nums2):
                if nums1[i] == nums2[j]:
                    i, j = i + 1, j + 1
                elif nums1[i] < nums2[j]:
                    i += 1
                    j += 1
            return res

  • 0

    Good point about using the shorter array to do the search. I went back after reading that and adjusted my code and it went from 72ms to 45ms!

    One question though, is there a particular reason why you import inside of the function VS at the top of the file? That idea is new to me.

    Here's my solution to this problem:

    from collections import Counter
    class Solution(object):
        def intersect(self, nums1, nums2):
            cnt_1, cnt_2 = sorted([Counter(nums1), Counter(nums2)])
            result = []
            for k, v in cnt_1.iteritems():
                current = cnt_2.get(k)
                if current is not None:
                    result.extend([k] * min(current, v))
            return result

Log in to reply

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