Merge Two Array in-place

1. Link

合并两个有序的数组_牛客题霸_牛客网www.nowcoder.com

2. 题目描述

给出两个有序的整数数组 和 ，请将数组 合并到数组 中，变成一个有序的数组 注意： 可以假设 数组有足够的空间存放 数组的元素， 和 中初始的元素数目分别为 和

3. 思路

1. 倒过来从尾部的元素开始对比A和B的最后一个元素

2. 把A和B的尾部的更大的元素添加到A array的尾部，因为A的array最后的n个位置是空的前m个位置才是A的元素

3. 不断重复知道A或B的元素被遍历完为止， 之后把A或B没有遍历的剩下的元素加到A array前面

4. Coding

#
# 
# @param A int整型一维数组 
# @param B int整型一维数组 
# @return void
#
class Solution:
    def merge(self , A, m, B, n):
        # write code here
        if not A and not B: 
            return []
        elif not A: 
            return B
        elif not B: 
            return A
        # start from the end of array
        while m > 0 and n > 0:
            if A[m-1] >= B[n-1]:
                A[m+n-1] = A[m-1]
                m-=1
            else:
                A[m+n-1] = B[n-1]
                n-=1
        if n > 0: 
            A[:n] = B[:n]
        return A