合并两个正序数组，原地操作，O(n)时间复杂度

ai提供的耳目一新的思路，今天分享一下

思路

A、B两数组，从后往前遍历两个数组：设置三个指针，两个分别指两个数组有数据的尾节点，另一个指向A的物理存储最后一个节点(A中至少有len（A+B）的空间)分别比较两个指针所指的尾节点数据，由大到小排列，从第三个指针的位置开始填充数据，直到覆盖到A中第一位。

代码

void mergeSortedArrays(int A[], int m, int B[], int n) {
    // 初始化三个指针
    int indexA = m - 1;  // 指向A中最后一个有效元素
    int indexB = n - 1;  // 指向B中最后一个有效元素
    int indexMerged = m + n - 1;  // 指向合并后的数组最后一个位置

    // 从后向前遍历，将较大的元素放到合并数组的末尾
    while (indexA >= 0 && indexB >= 0) {
        if (A[indexA] > B[indexB]) {
            A[indexMerged] = A[indexA];
            --indexA;
        } else {
            A[indexMerged] = B[indexB];
            --indexB;
        }
        --indexMerged;
    }

    // 如果B还有剩余元素，则将其复制到A中
    while (indexB >= 0) {
        A[indexMerged] = B[indexB];
        --indexB;
        --indexMerged;
    }

    // 如果A还有剩余元素，则不需要做任何事情，因为它们已经在正确的位置上
}

int main() {
    int A[] = {1, 3, 5, 0, 0, 0};  // 假设最后的0是为B预留的空间
    int B[] = {2, 4, 6};
    int m = 3;  // A的有效长度
    int n = 3;  // B的长度

    mergeSortedArrays(A, m, B, n);

    // 打印合并后的数组
    for (int i = 0; i < m + n; ++i) {
        printf("%d ", A[i]);
    }
    printf("\n");

    return 0;
}