合并排序的数组

题目链接

合并排序的数组

题目描述

注意点

• A的末端有足够的缓冲空间容纳B
• A和B都是排序的

解答思路

• 最初想到的是双指针，从小到大找到合并B时应该A相应位置应该插入的元素，因为在插入的过程中B的元素会替换A原有位置的元素，所以需要先将A中的元素赋值到C，再双指针根据B和C对应的元素值大小插入到A中
• 参照题解，因为A的末端有足够的缓冲空间容纳B，所以可以使用逆向双指针，先把更大的元素插入到A中，就不需要额外的空间存储A中的元素了

代码

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        int idxA = m - 1;
        int idxB = n - 1;
        while (idxA >= 0 || idxB >= 0) {
            if (idxA < 0) {
                A[idxA + idxB + 1] = B[idxB];
                idxB--;
                continue;
            }
            if (idxB < 0) {
                A[idxA + idxB + 1] = A[idxA];
                idxA--;
                continue;
            }
            if (A[idxA] > B[idxB]) {
                A[idxA + idxB + 1] = A[idxA];
                idxA--;
            } else {
                A[idxA + idxB + 1] = B[idxB];
                idxB--;
            }
        }
    }
}

关键点

• 双指针的思想