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). The result on my terminal is , but the result on leetcode OJ is .
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]
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 "," 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
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 =  Solution.merge(a, 0, b, 1)
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.
Input: , 
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 > 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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.