64. 合并排序数组

64. 合并排序数组

中文English

合并两个排序的整数数组A和B变成一个新的数组。

样例

样例 1:

输入：[1, 2, 3]  3  [4,5]  2
输出：[1,2,3,4,5]
解释:
经过合并新的数组为[1,2,3,4,5]

样例 2:

输入：[1,2,5] 3 [3,4] 2
输出：[1,2,3,4,5]
解释：
经过合并新的数组为[1,2,3,4,5]

注意事项

你可以假设A具有足够的空间（A数组的大小大于或等于m+n）去添加B中的元素。

 

 

输入测试数据 (每行一个参数)如何理解测试数据？

class Solution:
    """
    @param: A: sorted integer array A which has m elements, but size of A is m+n
    @param: m: An integer
    @param: B: sorted integer array B which has n elements
    @param: n: An integer
    @return: nothing
    """
    def mergeSortedArray(self, A, m, B, n):
        # write your code here
        #不用sort()解法
        
        #初始化
        poionA, poionB = m - 1, n - 1
        index = m + n - 1 
        
        #反向每次取最大
        #当两个数组可以相互比较最后一个值的大小的时候
        while poionA != -1 and poionB != -1:
            if (A[poionA] > B[poionB]):
                A[index] = A[poionA]
                poionA -= 1 
            else:
                A[index] = B[poionB]
                poionB -= 1 
            index -= 1 
            
        #最后剩下的直接加进来
        while poionA != -1:
            A[index] = A[poionA]
            index -= 1 
            poionA -= 1 
        
        while poionB != -1:
            A[index] = B[poionB]
            index -= 1
            poionB -= 1 
        
        return A