Merge Sorted Array Leetcode Python
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
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 nrespectively.
時間複雑度O(m+n)空間複雑度O(m+n)はまだより優れた方法がまだできていない.
新しい配列tmp集計方法でAとBの値の大きさを比較し、すべてtmpに格納します.最後にAを返します.
The time complexity and space complexity are both O(m+n). we use a new array tmp to store the value of A and B by order and then put it back to A. This problem can be treated as part of merge sort. The are some better methods, if you guys have it please leave it here.
Note:
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 nrespectively.
時間複雑度O(m+n)空間複雑度O(m+n)はまだより優れた方法がまだできていない.
新しい配列tmp集計方法でAとBの値の大きさを比較し、すべてtmpに格納します.最後にAを返します.
The time complexity and space complexity are both O(m+n). we use a new array tmp to store the value of A and B by order and then put it back to A. This problem can be treated as part of merge sort. The are some better methods, if you guys have it please leave it here.
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):
tmp=[0 for index in range(m+n)]
i=0
j=0
k=0
while i<m and j<n:
if A[i]<B[j]:
tmp[k]=A[i]
i+=1
else:
tmp[k]=B[j]
j+=1
k+=1
while i<m:
tmp[k]=A[i]
i+=1
k+=1
while j<n:
tmp[k]=B[j]
j+=1
k+=1
for index in range(m+n):
A[index]=tmp[index]
return A