合并两个有序数组的三种方式｜Java刷题打卡

本文正在参加「Java主题月 - Java 刷题打卡」，详情查看 活动链接

题目描述

这是 LeetCode 上的 88. 合并两个有序数组 。

Tag : 「双指针」、「排序」

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。

你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]
复制代码

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0

输出：[1]
复制代码

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -
  $10^9$

  109 <= nums1[i], nums2[i] <=

  $10^9$

  109

双指针（额外空间）

一个简单的做法是，创建一个和

nums1 等长的数组

arr，使用双指针将

num1 和

nums2 的数据迁移到

arr。

最后再将

arr 复制到

nums1 中。

代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int total = m + n;
        int[] arr = new int[total];
        int idx = 0;
        for (int i = 0, j = 0; i < m || j < n;) {
            if (i < m && j < n) {
                arr[idx++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            } else if (i < m) {
                arr[idx++] = nums1[i++];
            } else if (j < n) {
                arr[idx++] = nums2[j++];
            }
        }
        System.arraycopy(arr, 0, nums1, 0, total);
    }
}
复制代码

• 时间复杂度：
  $O(m + n)$

  O(m+n)

• 空间复杂度：
  $O(m + n)$

  O(m+n)

先合并再排序

我们还可以将

nums2 的内容先迁移到

nums1 去，再对

nums1 进行排序。

代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
    }
}
复制代码

• 时间复杂度：
  $O((m + n)log{(m + n)})$

  O((m+n)log(m+n))

• 空间复杂度：
  $O(1)$

  O(1)

PS. Java 中的 sort 排序是一个综合排序。包含插入/双轴快排/归并/timsort，这里假定 Arrays.sort 使用的是「双轴快排」，并忽略递归带来的空间开销。

原地合并（从前往后）

也可以直接在

nums1 进行合并操作，但是需要确保每次循环开始，

nums2 的指针指向的必然是最小的元素。

因此，我们需要对

nums2 执行局部排序。

代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0, j = 0;
        while (j < n) {
            if (i >= m) {
                nums1[i] = nums2[j++];
            } else {
                int a = nums1[i], b = nums2[j];
                if (a > b) swap(nums1, i, nums2, j);
                sort(nums2, j, n - 1);
            }
            i++;
        }
    }
    void sort(int[] nums, int l, int r) {
        if (l >= r) return;
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(nums, i, nums, j);
        }
        sort(nums, l, j);
        sort(nums, j + 1, r);
    }
    void swap(int[] nums1, int i, int[] nums2, int j) {
        int tmp = nums1[i];
        nums1[i] = nums2[j];
        nums2[j] = tmp;
    }
}
复制代码

• 时间复杂度：
  $O(n + m^2 log{m})$

  O(n+m2logm)

• 空间复杂度：忽略递归开销，复杂度为
  $O(1)$

  O(1)

原地合并（从后往前）

思路和「方法一」是类似的，将遍历方向由「从前往后」调整为「从后往前」即可做到

O(1) 空间复杂度。

代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1;
        int idx = m + n - 1;
        while (i >= 0 || j >= 0) {
            if (i >= 0 && j >= 0) {
                nums1[idx--] = nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--];
            } else if (i >= 0) {
                nums1[idx--] = nums1[i--];
            } else {
                nums1[idx--] = nums2[j--];
            }
        }
    }
}
复制代码

• 时间复杂度：
  $O(m + n)$

  O(m+n)

• 空间复杂度：
  $O(1)$

  O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.88 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。