一、题目
给你两个按 非递减顺序 排列的整数数组nums1
和nums2
,另有两个整数m
和n
,分别表示nums1
和nums2
中的元素数目。请你 合并 nums2
到nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意: 最终,合并后数组不应由函数返回,而是存储在数组nums1
中。为了应对这种情况,nums1
的初始长度为m + n
,其中前m
个元素表示应合并的元素,后n
个元素为0
,应忽略。nums2
的长度为n
。
示例 1:
输入: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
中的元素。
示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并[1]
和[]
。
合并结果是[1]
。
示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是[]
和[1]
。
合并结果是 [1]
。
注意,因为m = 0
,所以nums1
中没有元素。nums1
中仅存的0
仅仅是为了确保合并结果可以顺利存放到nums1
中。
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
进阶: 你可以设计实现一个时间复杂度为O(m + n)
的算法解决此问题吗?
二、代码
【1】直接合并后排序: 最直观的方法是先将数组nums2
放进数组nums1
的尾部,然后直接对整个数组进行排序。
class Solution {public void merge(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)log(m+n))
。排序序列长度为m+n
,套用快速排序的时间复杂度即可,平均情况为O((m+n)log(m+n))
。
空间复杂度: O(log(m+n))
。排序序列长度为m+n
,套用快速排序的空间复杂度即可,平均情况为O(log(m+n))
。
【2】双指针: 方法一没有利用数组nums1
与nums2
已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。我们为两个数组分别设置一个指针p1
与p2
来作为队列的头部指针。代码实现如下:
如果从右往左地把nums2
合并到nums1
中,是否会发生错误的覆盖呢?我们来看几个例子:
1、nums1=[1,2,3,∗,∗,∗]
,nums2=[4,5,6]
。这里我用∗
表示可以填入的空位。在这个例子中,nums2
可以直接填入nums1
后面的3
个空位,得到[1,2,3,4,5,6]
,没有任何错误覆盖。
2、nums1=[1,2,6,∗,∗,∗]
,nums2=[3,4,5]
。这里nums1
中的6
是最大的,应当填入末尾。现在nums1=[1,2,∗,∗,∗,6]
,注意nums1[2]
这个位置现在空出了。然后把nums2
中的数字填入空位,得到[1,2,3,4,5,6]
,没有任何错误覆盖。
3、上面的例子表明,把nums1
中的数字移到另一个空位,又产生了一个新的空位,所以剩余空位的个数是不变的,我们总是有空位可以让nums2
的数字填入,不会发生错误覆盖,这是如下算法正确的前提。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = 0, p2 = 0;int[] sorted = new int[m + n];int cur;while (p1 < m || p2 < n) {if (p1 == m) {cur = nums2[p2++];} else if (p2 == n) {cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {cur = nums1[p1++];} else {cur = nums2[p2++];}sorted[p1 + p2 - 1] = cur;}for (int i = 0; i != m + n; ++i) {nums1[i] = sorted[i];}}}
时间复杂度: O(m+n)
。指针移动单调递增,最多移动m+n
次,因此时间复杂度为O(m+n)
。
空间复杂度: O(m+n)
。需要建立长度为m+n
的中间数组sorted
。
【3】逆向双指针: 之所以要使用临时变量,是因为如果直接合并到数组nums1
中,nums1
中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖nums1
中的元素呢?观察可知,nums1
的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进nums1
的最后面。
严格来说,在此遍历过程中的任意一个时刻,nums1
数组中有m−mmax−1
个元素被放入nums1
的后半部,nums2
数组中有n−nmax−1
个元素被放入nums1
的后半部,而在指针mmax
的后面,nums1
数组有m+n−mmax−1
个位置。由于m+n−mmax−1≥m−mmax−1+n−nmax−1
等价于nmax≥−1
永远成立,因此mmax
后面的位置永远足够容纳被插入的元素,不会产生mmax
的元素被覆盖的情况。
class Solution {// 解题思路: 如果想重复利用 nums1的内存,可以从后先前替换,这样即不修改nums1之前的数据,还可以节省空间复杂度public void merge(int[] nums1, int m, int[] nums2, int n) {// 先做特殊情况的处理int mmax = nums1.length > m " />: nums1.length;int nmax = nums2.length > n ? n : nums2.length;// 从限定最大坐标(mmax和nmax)开始判断,将大的值存放到nums1最大的坐标(mmax+nmax)中while (mmax > 0 || nmax > 0) {// 如果 nmax <= 0 直接去 nums1 的值if(nmax <= 0 || (mmax > 0 && nums1[mmax - 1] > nums2[nmax - 1] )) {nums1[mmax + nmax - 1] = nums1[--mmax];} else {nums1[mmax + nmax - 1] = nums2[--nmax];}}}}
时间复杂度: O(m+n)
。指针移动单调递减,最多移动m+n
次,因此时间复杂度为O(m+n)
。
空间复杂度: O(1)
。直接对数组nums1
原地修改,不需要额外空间。
【4】标签: 从后向前数组遍历
1、因为nums1
的空间都集中在后面,所以从后向前处理排序的数据会更好,节省空间,一边遍历一边将值填充进去。
2、设置指针len1
和len2
分别指向nums1
和nums2
的有数字尾部,从尾部值开始比较遍历,同时设置指针len
指向nums1
的最末尾,每次遍历比较值大小之后,则进行填充。
3、当len1<0
时遍历结束,此时nums2
中海油数据未拷贝完全,将其直接拷贝到nums1
的前面,最后得到结果数组。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int len1 = m - 1;int len2 = n - 1;int len = m + n - 1;while(len1 >= 0 && len2 >= 0) {// 注意--符号在后面,表示先进行计算再减1,这种缩写缩短了代码nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];}// 表示将nums2数组从下标0位置开始,拷贝到nums1数组中,从下标0位置开始,长度为len2+1System.arraycopy(nums2, 0, nums1, 0, len2 + 1);}}
时间复杂度: O(m+n)