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

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--];
        }

        // 如果A中还有剩余元素，它们已经在正确的位置上，不需要额外处理
    }
};

这是一个数组合并问题，需要将有序数组B合并到有序数组A中，并保持有序。由于数组A有足够的空间，我们可以从后往前填充，避免频繁移动元素。

解题思路

1. 双指针法：使用三个指针分别指向：数组A的最后一个有效元素位置（m-1）数组B的最后一个元素位置（n-1）合并后数组的最后一个位置（m+n-1）
2. 从后往前比较：比较两个数组当前的最大元素，将较大的元素放到合并后数组的末尾
3. 处理剩余元素：如果数组B还有剩余元素，直接复制到数组A的前面