Below is my solution for merge of two sorted arrays A,B. I implemented the merge section of merge sort, but for some reason the system does not accept my solution and points it has a wrong answer for input  . The algorithm return  when I run it in my machine. But the system gets an output of  for this input. Not sure what is wrong with the code. Any help would be useful. Thanks
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): sorted_array =  if m>0 and n > 0: i,j = 0,0 while i < m and j < n: if A[i] < B[j]: sorted_array.append(A[i]) i += 1 else: sorted_array.append(B[j]) j += 1 if j == n: sorted_array.extend(A[i:]) else: sorted_array.extend(B[j:]) #assigning back to A A = sorted_array elif B: A = B return
I met this problem 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
I do think OJ has some thing not quite right with List.extend(). Even though in local python env list.extend(L) is equivalent to list[len(list):] = L, it is not the case when OJ judges the answer. I am not sure why though, has to do with how the backend processes the answer and test cases.
See my example below, note the comment.
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): i = m-1 j = n-1 # change this line to A.extend(B) and it falls apart A[m:] = B for x in range(len(A)-1, -1, -1): if i >= 0 and j >= 0: if A[i] > B[j]: A[x] = A[i] i -= 1 else: A[x] = B[j] j -= 1 elif j >= 0: A[x] = B[j] j -= 1 else: break
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.