Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Example
A = [1, 2, 3, empty, empty], B = [4, 5]
After merge, A will be filled as [1, 2, 3, 4, 5]
Solution:
(1) 第一种方法, O(n2)复杂度,因为每次对比当前的两个数组的索引对应的两个值,如果B里面的小,这时需要插入进入数组,整体右移动数组,然后插入,
(2) 可以利用数组长度正好等于 m + n , 把大的值直接放到最右边,这样可以省去移动操作。
class Solution:
"""
@param A: sorted integer array A which has m elements,
but size of A is m+n
@param B: sorted integer array B which has n elements
@return: void
"""
def mergeSortedArray(self, A, m, B, n):
# write your code here
i, j, k = m - 1, n - 1, m + n - 1
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 i >= 0:
A[k] = A[i]
k -= 1
i -= 1
while j >=0:
A[k] = B[j]
k -= 1
j -= 1
Last updated
Was this helpful?