合并两个有序数组

package com.memorys.algorithm.year2021.month08;

/** * @Date 2021-08-09 23:07 * @Description: * * 合并两个有序数组 * * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 * * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。 * * 作者：力扣 (LeetCode) * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xmi2l7/ * 来源：力扣（LeetCode） * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 * */public class Merge {
    public static void main(String[] args) {
        int[] nums1 = {1,2,3,0,0,0};        int[] nums2 = {2,5,6};        int m = 3;        int n = 3;        merge1(nums1,nums2,m,n);
        for (int i = 0; i < nums1.length; i++) {            int i1 = nums1[i];            System.out.print(i1 + ",");        }
    }

    /**     * @CreateDate 2021-08-09 23:25     * @param nums1     * @param nums2     * @param m     * @param n     * @Description :     * 排序的思路，一般都是从小到大排序。     * 但是在这里会发现，如果是从小到大排序的话，不使用额外的空间，肯定会产生数字的位移。     * 那么一旦需要做位移，就很可能出现平方级的 时间复杂度，，     *     * 但是这里发现题目中  num1 数组后方刚好空余出了 n长度的位置，     * 刚好可以放下 num2     * 因此，可以发现如果从大到小去排序的话，是不会出现元素被追上导致需要位移的情况。     *     * 本例中的答案就是从大往小排序。     *     * @Return void     */    private static void merge1(int[] nums1, int[] nums2, int m, int n) {
        boolean flag = true;
        int position = m + n - 1;
        while (flag){
            if (m > 0 && n > 0){                if (nums1[m-1] > nums2[n-1]){                    nums1[position] = nums1[m-1];                    position--;                    m--;                } else {                    nums1[position] = nums2[n-1];                    position--;                    n--;                }            }

            if (m == 0 && n > 0){                nums1[position] = nums2[n-1];                position--;                n--;            }

//            // 这段代码可以省略赋值操作，因为最后剩下的num1 赋值或者不赋值，都是在原位置。            if (n == 0 && m > 0){//                nums1[position] = nums1[m-1];//                position--;//                m--;                m = 0;            }

            // 循环结束条件 num1 和 num2 都遍历结束了            if (m == 0 && n == 0){                flag = false;            }        }    }}