【LeetCode】88. 合并两个有序数组
![](https://storage.bummon.com/image/202308301814501.png)
【LeetCode】88. 合并两个有序数组
Bummon88. 合并两个有序数组
题目
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意: 最终,合并后数组不应由函数返回,而是存储在数组 nums1
中。为了应对这种情况,nums1
的初始长度为 m + n
,其中前 m
个元素表示应合并的元素,后 n
个元素为 0
,应忽略。nums2
的长度为 n
。
示例 1:
1 | 输入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 |
示例 2:
1 | 输入: nums1 = [1], m = 1, nums2 = [], n = 0 |
示例 3:
1 | 输入: nums1 = [0], m = 0, nums2 = [1], n = 1 |
提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
双指针法
思路分析
我们查看题目可以知道:nums1
和 nums2
均为非递减数组,那我们只需要将每个元素逐一比较即可。
nums1
的初始长度设为 mergeIndex = m + n - 1
,我们将 nums1
真正的最后一个元素下标设为 mIndex = m - 1
,nums2
最后一个元素下标设为 nIndex = n - 1
,我们从尾部开始遍历比较,以免从头部开始遍历比较时填入元素会将未比较的元素覆盖掉的情况。
例子中举例有可能存在 m = 0
或 n = 0
的情况,那么我们的 mIndex
和 nIndex
有可能存在负数的情况,我们也要进行处理,如下:
- 当
nums1[mIndex] > nums2[nIndex]
时,那么我们将值较大的nums1[mIndex]
填充到nums1
的mergeIndex
处。 - 当
nums1[mIndex] < nums2[nIndex]
时,我们可以将值比较大的nums2[nIndex]
填充到nums1
的mergeIndex
处。 - 当
m < 0
时,则说明nums1[mIndex]
没有值,则将nums2[nIndex]
的值放到nums1
的mergeIndex
处。
注意:题目中提到了 0 <= m, n <= 200
,且 1 <= m + n <= 200
,则说明 m
和 n
不可同时为 0,那么我们就可以不处理这个情况。
图解
代码实现
1 | public static int[] merge(int[] nums1, int m, int[] nums2, int n) { |
总结
使用 双指针法
解决该问题时,我们可以看到两个数组至多循环 n 次,那么时间复杂度为 O(n)。
我们共使用了三个额外变量:mIndex
、nIndex
和 mergeIndex
,则空间复杂度为 O(1)。
评论
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果