题解 | 合并两个有序的数组

1、解题思路

1. 合并两个有序数组 ：由于数组 A 和 B 都是有序的，可以利用双指针的方法，分别从数组 A 和 B 的末尾开始比较，将较大的元素放到数组 A 的末尾。
2. 处理剩余元素 ：如果数组 B 还有剩余元素，直接将其复制到数组 A 的前面。如果数组 A 还有剩余元素，由于数组 A 本身是有序的，不需要额外处理。

2、代码实现

C++

class Solution {
  public:
    void merge(int A[], int m, int B[], int n) {
        int i = m - 1;  // 数组 A 的末尾指针
        int j = n - 1;  // 数组 B 的末尾指针
        int k = m + n - 1;  // 合并后的数组末尾指针

        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[k--] = A[i--];
            } else {
                A[k--] = B[j--];
            }
        }

        // 如果数组 B 还有剩余元素, 直接复制到 A 前面
        while (j >= 0) {
            A[k--] = B[j--];
        }
    }
};

Java

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int i = m - 1; // 数组 A 的末尾指针
        int j = n - 1; // 数组 B 的末尾指针
        int k = m + n - 1; // 合并后的数组末尾指针
        
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[k--] = A[i--];
            } else {
                A[k--] = B[j--];
            }
        }
        
        // 如果数组 B 还有剩余元素，直接复制到 A 的前面
        while (j >= 0) {
            A[k--] = B[j--];
        }
    }
}

Python

#
# 
# @param A int整型一维数组 
# @param B int整型一维数组 
# @return void
#
class Solution:
    def merge(self , A, m, B, n):
        # write code here
        i = m - 1  # 数组 A 的末尾指针
        j = n - 1  # 数组 B 的末尾指针
        k = m + n - 1  # 合并后的数组末尾指针
        
        while i >= 0 and j >= 0:
            if A[i] > B[j]:
                A[k] = A[i]
                i -= 1
            else:
                A[k] = B[j]
                j -= 1
            k -= 1
        
        # 如果数组 B 还有剩余元素，直接复制到 A 的前面
        while j >= 0:
            A[k] = B[j]
            j -= 1
            k -= 1

3、复杂度分析

• 时间复杂度：O(m + n)，其中 m 和 n 分别是数组 A 和 B 的长度。每个元素最多被处理一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。