Concise Python solutions


  • 0
    C

    Several people have posted the variations of this two-liner solutions using python's sort :

     def merge(self, nums1, m, nums2, n):
        nums1[m:] = nums2[:n]
        nums1.sort()
    

    Here I'm providing some easy-to-understand and short solutions:

    **(1) 6 lines, 52ms.**
    We know there will be `m` elements from `nums1` and `n` elements from `nums2`. We can simply iterate over nums2 and insert elements into `nums1`. The `i < m+j` condition can make sure we never use more than m elements from nums1.
    def merge(self, nums1, m, nums2, n):
        i, j = 0, 0
        for j in range(n):
            while i < m+j and nums2[j] > nums1[i]:
                i += 1
            nums1.insert(i, nums2[j])
        nums1[m+j+1:] = nums2[j+1:]
    

    **(2) 8 lines, 44 ms.**
    This is almost the same as previous one. I just added two lines to terminate the `for` loop earlier as soon as we have used up all the `m` elements we need from `nums1`. It runs a little bit faster than the previous one.
    def merge(self, nums1, m, nums2, n):
        i, j = 0, 0
        for j in range(n):
            while i < m+j and nums2[j] > nums1[i]:
                i += 1
            nums1.insert(i, nums2[j])
            if i == m + j:
                break
        nums1[m+j+1:] = nums2[j+1:]

  • 0

    Using insert is not so good, makes this O(mn) instead of the O(m+n) it could be.


  • 0
    C

    Yeah, you are right! Forget insert is O(n). This solution would be slower when m or n is very large. Thanks!


Log in to reply
 

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