220426合并两个有序数组

    public static void main(String[] args) {
        int[] num1 = new int[]{1,3,5,7,9,0,0,0,0};
        int[] num2 = new int[]{2,4,5,8};
        System.out.println(Arrays.toString(merge(num1,5,num2,4)));
    }
    /**
     * 时间复杂度是 (m+n)log(m+n)
     * @param num1
     * @param m
     * @param num2
     * @param n
     * @return
     */
    private static int[] merge(int[] num1, int m, int[] num2, int n) {
        System.arraycopy(num2,0,num1,m,n);
        Arrays.sort(num1);
        return num1;
    }

public static void main(String[] args) {

        int[] num1 = new int[]{1,3,5,7,9,0,0,0,0};
        int[] num2 = new int[]{2,4,5,10};

        System.out.println(Arrays.toString(merge1(num1,5,num2,4)));

    }

    /**
     * 创建一个新数组，将num1中的数据复制过去，然后使用双指针比较新数组和num2的数据大小将数据写入num1中
     * 时间复杂度O(n)，空间复杂度O(n)
     * @param num1
     * @param m
     * @param num2
     * @param n
     * @return
     */
    private static int[] merge1(int[] num1, int m, int[] num2, int n) {
        int[] num_temp = new int[m];
        // 将num1中的数据复制到临时数组中
        System.arraycopy(num1,0,num_temp,0,m);
        int index1 = 0,index2 = 0,index_temp = 0;
        // 循环，当临时数组或num2数组中有一个的数据都放入num1中，则终止循环
        while (index_temp < m && index2 < n) {
            num1[index1++] = num_temp[index_temp] > num2[index2] ? num2[index2++] : num_temp[index_temp++];
        }
        // 满足条件，说明num2数组先合并完成，将num_temp剩余的数据直接复制到num1中
        if (index_temp < m) {
            System.arraycopy(num_temp,index_temp,num1,index1,m - index_temp);
        }
        // 满足条件，说明num_temp数组先合并完成，将num2剩余的数据直接复制到num1中
        if (index2 < n) {
            System.arraycopy(num2,index2,num1,index1,n - index2);
        }

        return num1;
    }

public static void main(String[] args) {

        int[] num1 = new int[]{3,4,5,7,9,0,0,0,0};
        int[] num2 = new int[]{2,4,5,10};

        System.out.println(Arrays.toString(merge2(num1,5,num2,4)));

    }

    /***
     * 使用双指针从数组后往前遍历，然后从num1的后面开始存放
     * 时间复杂度O(n)
     * @param num1
     * @param m
     * @param num2
     * @param n
     * @return
     */
    private static int[] merge2(int[] num1, int m, int[] num2, int n) {
        int index1 = m - 1,index2 = n - 1, index_sum = m + n - 1;

        while (index1 >= 0 && index2 >= 0) {
            num1[index_sum--] = num1[index1] > num2[index2] ? num1[index1--] : num2[index2--];
        }
        // 满足条件，说明num1数组先合并完成，将num2剩余的数据直接复制到num1中
        if (index2 >= 0) {
            System.arraycopy(num2,0,num1,0,index2 + 1);
        }

        return num1;
    }