[数据结构与算法]LeetCode88

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列
。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n

链接：

思路

定义 三个指针 指针k 负责存储元素，指针i 负责遍历nums1 指针j 负责遍历nums2；
因为题意说明合并的结果是放到nums1 中 两个数组是非递减的数组，说明数组的第一位是当前数组的最小的一位，最后一个是最大的一位，
如果从前往后开始遍历数组会发现如果nums2 的元素前面几个都比nums1 中的元素小的话会把 nums1中的元素覆盖调，所以不能从前往后遍历
可以使用从后往前遍历的方式。指针k 初始位置在m+n-1 位置 指针 i 在m-1 位置， 指针j 在n-1的位置上
使用循环 两个指针 i/j 开始比较 ，那个指针的值大 则那个指针的值放到指针k 的位置 ，则k–。指针大的指针向后移动一位，
继续比较两个指针的大小，重复上面操作，
如果 指针i 已经走完则需要再次循环把 nums2的元素继续插着到第一个数组中。
如果 指针j 先走完则说明 合并完毕。

空间复杂度 o（1）（没有使用到额外的空间）
时间复杂度 o（m+n）最坏情况，第一个数组全部移动，第二个数组怎么都需添加到第一个数组中 则最坏的情况是o(m+n).
最理想情况是第一个数组都比第二数组小，则最好情况是o（n）

代码演示

public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n - 1;
        int i = m - 1;
        int j = n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        while(j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
    public static void main(String[] args) {
        int[] a = {1,2,3,0,0,0};
        int[] b = {4,5,6};
        merge(a, 3, b, 3);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }