Why My Python Code Wrong?


  • 1
    L

    Hi,this is my merge sort code written in python.I don't know why it gets the wrong answer on the server.But it really works rightly on my PC!!My python version is 2.7.3,running on a ubuntu system,the IDE is PyDev.Thanks

    Input: [], [1]

    Output: [0]

    Expected: [1]

    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):
            mLa=[] # A tmp list for storing with Merge Sort result
            m = len(A)# Make sure the params m and n are both right
            n = len(B)
            # Handle some specials where m or n equals 0
            if n==0:
                return
            if m==0:
                for i in range(n):
                    A.append(B[i])
                return
            
            ia = 0 # Index digits for A and B
            ib = 0
            # Detect whether the sorted lists are big-endian or little-endian
            if m>1:
                bigEndian = (A[ia]<A[ia+1])
            elif n>1:
                bigEndian = (B[ib]<B[ib+1])
            else:
                bigEndian = True
            #Begin Merge Sort:do 'while' until ia or ib arrives at its end
            while ia<m and ib<n:
                if A[ia]<=B[ib]:
                    if bigEndian:#If big-endian,append little one first
                        mLa.append(A[ia])
                        ia += 1
                    else:#else,append bigger one fisrt
                        mLa.append(B[ib])
                        ib += 1
                    
                else:
                    if bigEndian:
                        mLa.append(B[ib])
                        ib += 1
                    else:
                        mLa.append(A[ia])
                        ia += 1
            # Merge un-merged elements
            if ia == m:
                for i in range(ib,n):
                    mLa.append(B[i])
            else:
                for i in range(ia,m):
                    mLa.append(A[i])
            #Copy the beginning m elements of mLa to A
            for i in range(m):
                A[i] = mLa[i]
            #Append the rest of mLa to A
            for j in range(m,m+n):
                A.append(mLa[j])

  • 2
    S

    I see some append is being used.

    In problem description, it says

    You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

    This means no append is needed. A is already big enough to save all element. Its index is available between m + 1 and m + n


  • 0
    L

    Thanks,it works now.It's really a stupid mistake that I didn't read the question carefully.


  • 0
    G

    thank you, you solved my problem


  • 0
    S

    That is why I always get error in my computer?
    ->nums1[end] = nums2[l2]
    ->IndexError: list assignment index out of range

    def merge(self, A, m, B, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        l1, l2, end = m - 1, n - 1, m + n - 1
        while l1 >= 0 and l2 >= 0:
        	if nums2[l2] > nums1[l1]:
        		nums1[end] = nums2[l2]
        		l2 -= 1
        	else:
        		nums1[end] = nums1[l1]
        		l1 -= 1
        	end -= 1
        if l1 < 0:
        	nums1[:l2 + 1] = nums2[:l2 + 1]

Log in to reply
 

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