What's wrong with my code? I cannot get correct results but on my local terminal.(Merge Sorted Array)


  • 0
    J

    I ran my code on my terminal and leetcode OJ respectively, but I can only get correct result on my terminal.
    For instance input is ( [],0,[1],1). The result on my terminal is [1], but the result on leetcode OJ is [0].
    I don't know why. Is the reason that leetcode cannot use append and extend?

    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 i in range(0,n):
                A.append(B[i])
        elif n == 0:
            pass
        else:
            C = []
            a = 0
            b = 0
            while(a < m and b < n):
                if A[a] <= B[b]:
                    C.append(A[a])
                    a += 1
                else:
                    C.append(B[b])
                    b += 1
            if a == m:
                C.extend(B[b:])
            else:
                C.extend(A[a:])
            for x in range(0,m+n):
                A[x] = C[x]

  • 3
    W

    Many people met this problem. Me, too. But after reading the problem again, I notice that we should merge B into A without create a new array. Maybe this is the reason why our code can not pass the "[],[1]" input. And the following is my ac code. Wish it can help you.

    class Solution:
        def merge(self, A, m, B, n):
    
            i = m - 1
            j = n - 1
            k = m + n - 1
    
            for num in range(m, m+n):
                A.insert(num, 0)
    
            while i >= 0 and j >= 0:
                if A[i] > B[j]:
                    A[k] = A[i]
                    k -= 1
                    i -= 1
                else:
                    A[k] = B[j]
                    k -= 1
                    j -= 1
            while j >= 0:
                A[k] = B[j]
                k -= 1
                j -= 1
    

  • 2
    M

    Me too.
    And I am sure that I merge B to A without creating another List.
    Here is my code:

    class Solution:
      def merge(self, A, m, B, n):
        indexA = 0
        indexB = 0
    
        while indexA < m and indexB < n:
          cA = A[indexA]
          cB = B[indexB]
          if cA >= cB:
            A.insert(indexA, cB)
            m = m + 1
            indexB = indexB + 1
            continue
          indexA = indexA + 1
    
        while indexB < n:
          A.append(B[indexB])
          indexB = indexB + 1
    a = []
    b = [1]
    Solution.merge(a, 0, b, 1)
    

  • 0
    Y

    I also have the same problem. I merge B into A by insert, similar algorithm as yours, however, there are several tests run differently on leetcode and my machine.


  • 0
    A

    Input: [], [1]
    Output: [0]
    Expected: [1]
    here is my code passed on local but get wrong answer in ac test. can anybody tell me why ? - new python coder.

    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 i in range(0, n):
                A.append(B[i])
        if n == 0:
            pass
        elif B[0] > A[m-1]:
            A.extend(B)
        else: # complex part
            temp = 0    # save list B[i] item for compare with A[j]
            k = 0       # save the insert index for temp 
            # loop A from higher to lower, both dynamic change based on previous value
            higher = m - 1  
            lower = 0  
            
            for i in range(0, n):  # loop list B
                for j in range(lower, higher+1)[::-1]: # loop list A in reverse order
                    if (B[i] < A[j]):
                        temp = B[i] # save current value for comparing
                        k = j   
                        A.append(A[k])
                        # move list A to right
                        while k > 0 and temp < A[k-1]:
                            A[k] = A[k-1]
                            k-=1
                        # insert temp to appropriate position
                        A[k] = temp
                        higher = m + i
                        lower = k
                        break
                    else:   # append B[i] to list A and change higher and lower value
                        A.append(B[i])
                        higher = m + i
                        lower = j + 1
                        break
    

Log in to reply
 

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