Python WA:Input: [], [1] Output: [0] Expected: [1]


  • 1
    M

    I wonder whether there are some problems with python code in this problem. I tested the input [], [1] in my local environment and get the right answer. But when I submit the code to the oj I got [0], which confused me. Could anyone give me some idea? My code are as follow:

    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):
        pa = 0
        pb = 0
        while len(A) != pa and len(B) != pb:
            if A[pa] > B[pb]:
                A.insert(pa,B[pb])
                pb += 1
            else:
                pa += 1
        while len(B) != pb:
            A.insert(pa,B[pb])
            pb += 1
            pa += 1
        return A

  • 2
    M
    # @return nothing
    

    A is not actually [], though it claims to be. In order to be able to return nothing, A needs space for all of B (so long as you can't modify the length of an array). Because of this, in this case, A is [0], with m=0, while the input with A=[0], m=1 would be written as A=[0] as well, so long as B=[],n=0.

    The judge for this problem knows how many elements are required, so it looks in its array, which gets passed to A, and checks the first m+n slots. Since m=0,n=1, it checks the first slot, which is the least number in your array, the [0]. Instead of using len(A) or len(B), use m and n instead.


    SPOILER

    This trick for a linear solution is to fill the arrays from the end back to the start.


  • 0
    M

    Thanks! My code was acceped with your advice!


  • 0
    P

    hi @maplewizard , I have exact the same question with you in my python solution. So what did you do to make it pass? I still don't understand very well after reading the answer. Thanks.


  • 0
    M

    Hello paullo, my code is as follow, please note that I have replaced all len(A) and len(B) with m and n, the reason for this was explained by mike3. If you just can't understand why, just replace them and remember do not apply len() function to input list, use the length given by the parameter instead. good luck.

    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):
        pa = 0
        pb = 0
        d = 0
        while m+d != pa and n != pb:
            if A[pa] > B[pb]:
                A.insert(pa,B[pb])
                pb += 1
                d += 1
            pa += 1
        while n != pb:
            A.insert(pa,B[pb])
            pb += 1
            pa += 1
        return A

  • 0
    P

    Thanks very much, it's really tricky :p


Log in to reply
 

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