Can anyone help me to find out what's wrong with my code ?(Merge Sorted array)


  • 0
    J
    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):
        if m == 0:
            for j in range(0,n):
                A.append(B[j])
                #A[j] = B[j]
        else:
            C = []
            while((len(A)*len(B)) != 0):
                if A[0] <= B[0]:
                    C.append(A.pop(0))
                else:
                    C.append(B.pop(0))
            if len(A) != 0:
                for i in range(0,len(A)):
                    C.append(A[i])
            elif len(B) != 0:
                for i in range(0,len(B)):
                    C.append(B[i])
            for k in range(0,len(C)):
                A.append(C[k])

  • 2
    M

    There are several issues in this.

    1. Append adds to the end of the array, which is fine, except, since this is the same input as with Java, A already has enough room for m+n elements, despite only having m elements itself. Instead of using append in the first portion, you need to put them in the correct position, such as A[j]=B[j], as you've commented out.

    2. Similarly, len(A) is m+n at the start, but the array we care about is only m. Instead of using len(A) and len(B), use m and n and decrement them when you pop something from their array.

    3. Once again, append adds to the end of the array. If A is non-empty, such as in the case where m>n, the loop copies the end of A onto C, but does not remove the elements from A, so the final for loop still has those elements at the start of the array when it starts copying its content onto the end of A.

    4. At the very least, this algorithm takes 2(m+n) steps to complete, with each step being an append operation. While this might work, there is an m+n step solution, with each step being an assign, which is a much faster operation than append.


  • 0
    J

    Got it. Thank you so much!


Log in to reply
 

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