【算法】合并两个有序数组 - 双指针

题目

两个有序整数数组 nums1 和 nums2 及他们的元素个数 m、n，将 nums2 合并到 nums1 中，结果依然有序。
nums1 长度默认为 m + n，没有元素的位置用 0 补齐。

原理

定义三个指针，分别指向 nums1 的最大元素(p1)、nums2 的最大元素(p2)、nums1 的最后一个元素(空位)(p)。依次对比 p1 和 p2 的大小，大的放到 p 的位置，前移已经移动的指针和 p 指针即可。

代码

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 3, 5, 7, 9, 0, 0, 0, 0};
        int[] nums2 = new int[]{2, 4, 6, 8};
        combineArray(nums1, 5, nums2, 4);
        System.out.println(Arrays.toString(nums1));
    }

    private static void combineArray(int[] nums1, int m, int[] nums2, int n) {
        int p = nums1.length - 1, p1 = m - 1, p2 = n - 1;
        while (p1 >= 0 && p2 >= 0) {
            nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
    }