合并两个有序的数组

问题简述

给定两个有序数组 A 和 B，请将数组 B 合并到数组 A 中；
A 和 B 中初始的元素数目分别为 m 和 n，A 的数组空间大小为 m + n；
要求不使用额外空间。

合并两个有序的数组_牛客题霸_牛客网

思路

• 双指针 + 逆序填空；

Python

#
# 
# @param A int整型一维数组 
# @param B int整型一维数组 
# @return void
#
class Solution:
    def merge(self , A, m, B, n):
        # write code here
        i, j = m - 1, n - 1
        p = m + n - 1
        
        while i >= 0 and j >= 0:
            if A[i] > B[j]:
                A[p] = A[i]
                i -= 1
            else:
                A[p] = B[j]
                j -= 1
            p -= 1
        
        while j >= 0:
            A[p] = B[j]
            j -= 1
            p -= 1