Python solutino -- Please someone tell me why my solution fail when input is [],[1]??


  • 0
    J

    def merge(self, A, m, B, n):
    if m == 0 or A == []:
    return B
    elif n == 0 or B == []:
    return A
    else:
    A.extend(B)
    A.sort()
    return A

    My code is above, I changed several ways to merge this two arrays, but all failed when input is [] and [1].
    And I ran this code in my idle, which come out with right answer when [] and [1]..

    Somebody tell me the reason?


  • 1
    D

    First, the merge method doesn't return anything, it will check the array A. So u need to understand the problem a little bit clearer.
    A is array sorted from index 0 to m (exclusive), B is sorted from 0 to n. A might have more elements after the index m. In your test case, A = [0] , not [].B=[1].

    Second, ur method run in nlogn (using sort).
    You can refer to the below code for improvement.

    class Solution:
        # @param A  a list of integers
        # @param m  an integer, length of A
        # @param B  a list of integers
        # @param n  an integer, length of B
        # @return nothing
        def merge(self, A, m, B, n):
            
            #we merge from the end of array A
            l = m+n - 1 #last element
            m = m-1
            n = n-1
            while(m>=0 and n>=0):
                if(A[m] > B[n]):
                    A[l] = A[m]
                    m = m-1
                else:
                    A[l] = B[n]
                    n = n-1
                l = l - 1
                
            #don't need to do this for m
            while(n>=0):
                A[l] = B[n];
                n = n-1
                l = l-1

  • 0
    J

    perfect idea, I also was just doing solution similar to you. But I met two problems: 1. how to identify A, B is [] or not? 2. and wrong output when input are [],[1]...
    your answer perfectly resolve my problems. 1. use respectively length m,n to identify [] 2. consider one more situation that after merged, B still has elements in it...
    Thanks!!


  • 0
    H

    you do not need l in the second loop. l must be n.
    so one line can be saved


Log in to reply
 

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