88. 合并两个有序数组

题目

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

解题方法一

 /**
     * 调用类库API
     * 1.数组间的复制
     * public static native void arraycopy(Object src,  int srcPos, Object dest, int destPos, int length);
     * 参数说明：
     * Object src：the source array. 源数组
     * int srcPos：starting position in the source array. 在源数组中，开始复制的位置
     * Object dest：the destination array. 目标数组
     * int destPos：starting position in the destination data. 在目标数组中，开始赋值的位置
     * int length：the number of array elements to be copied. 被复制的数组元素的数量
     *
     * 2.数组排序
     * Arrays.sort(array);
     *
     * 3.完成返回
     *
     * 执行用时：1 ms, 在所有 Java 提交中击败了14.01%的用户
     * 内存消耗：41.5 MB, 在所有 Java 提交中击败了5.01%的用户
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 处理边界条件
        if (m == 0 && n == 0) return;
        if (m == 0){
            // public static native void arraycopy(Object src,  int srcPos, Object dest, int destPos, int length);
            // 它是一个静态本地方法，由虚拟机实现，效率自然比用java一个个复制高。
            // 从源数组src取元素，范围为下标srcPos到srcPos+length-1，取出共length个元素，存放到目标数组中，存放位置为下标destPos到destPos+length-1。
            if (n >= 0) System.arraycopy(nums2, 0, nums1, 0, n);
        }
        if (n == 0) return;
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
    }

解题方法二

/**
     * 直接合并后排序
     *
     * 时间复杂度：O((m+n)log(m+n))。
     * 排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n))。
     * 空间复杂度：O(log(m+n))。
     * 排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge2(int[] nums1, int m, int[] nums2, int n){
        // 合并数组
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        // 数组排序
        Arrays.sort(nums1);
    }

解题方法三

/**
     * 双指针
     *
     * 时间复杂度：O(m+n)。
     * 指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
     *
     * 空间复杂度：O(m+n)。
     * 需要建立长度为 m+n 的中间数组 sorted。
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge3(int[] nums1, int m, int[] nums2, int n){
        int p1 = 0, p2 = 0; // 分别指向nums1,nums2的指针
        int[] sorted = new int[m + n]; // 辅助数组 暂存已排序数组元素
        int cur; // 此次确定添加到sorted的元素
        while (p1 < m || p2 < n){ // 保证两数组全部遍历完
            if (p1 == m){  // nums1 遍历结束
                cur = nums2[p2++];
            }else if(p2 == n){   // nums2 遍历结束
                cur = nums1[p1++];
            }else if (nums1[p1] <= nums2[p2]){ // 两数组都没遍历完 比较大小
                cur = nums1[p1++];
            }else {
                cur = nums2[p2++];
            }
            // 最后将确定的元素添加到辅助数组
            sorted[p1 + p2 - 1] = cur;
        }
        // 拷贝辅助数组到nums1
        System.arraycopy(sorted,0,nums1,0,sorted.length);
    }

解题方法四

/**
     * 逆向双指针
     *
     * 时间复杂度：(m+n)。
     * 指针移动单调递减，最多移动 m+n次，因此时间复杂度为 O(m+n)。
     *
     * 空间复杂度：O(1)。
     * 直接对数组 nums1原地修改，不需要额外空间。
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge4(int[] nums1, int m, int[] nums2, int n){
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }

微信关注

WeChat