LeetCode 88、合并两个有序数组
LeetCode 88、合并两个有序数组
一、题目描述
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
二、题目解析
设置两个索引 i 和 j 分别指向 nums1 和 nums2 的有效元素的尾部，从它们的尾部开始向前遍历，同时设置索引 cur 指向 nums1 的最末尾，在每次遍历过程中，比较 i 和 j 指向的元素值大小，把大的元素填充到 cur 的位置，填充完毕说明那个元素已经放置在它应该放置的位置，不需要在管它了，把 cur 向前移动，同时把 i 或者 j 向前移动，继续比较 i 和 j 指向的元素值大小，把大的元素填充到 cur 的位置。
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/555.html
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并两个有序数组( LeetCode 88 ):https://leetcode-cn.com/problems/merge-sorted-array/
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 索引从有序数组 nums1 有效元素的末端开始
// 数组的下标索引从零开始计数
// 索引 0 1 2
// 数组 [ 1 , 2 , 3 ]
int i = m - 1;
// 索引从有序数组 nums2 的末端开始
int j = n - 1;
// 从有序数组 nums1 最末端的位置开始保存元素
int cur = nums1.length - 1;
// 通过循环把 num2 的元素都移动到 num1 中
while( j >= 0 ){
// 比较 num1 和 num2 中当前的元素大小
// 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
// 为了防止越界 i 必须是大于等于 0
if( i >=0 && nums1[i] > nums2[j] ){
// 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
// 此时 cur 的元素已经确定下来
nums1[cur] = nums1[i];
// 接下来去确定 cur 前面一个元素应该放什么数字
cur--;
// 此时，索引 i 需要向前移动
i--;
// 否则，如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
}else{
// 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
nums1[cur] = nums2[j];
// 接下来去确定 cur 前面一个元素应该放什么数字
cur--;
// 此时，索引 j 需要向前移动
j--;
}
}
}
}2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com/555.html
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 合并两个有序数组( LeetCode 88 ):https://leetcode-cn.com/problems/merge-sorted-array/
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 索引从有序数组 nums1 有效元素的末端开始
// 数组的下标索引从零开始计数
// 索引 0 1 2
// 数组 [ 1 , 2 , 3 ]
int i = m - 1;
// 索引从有序数组 nums2 的末端开始
int j = n - 1;
// 从有序数组 nums1 最末端的位置开始保存元素
int cur = nums1.size() - 1;
// 通过循环把 num2 的元素都移动到 num1 中
while( j >= 0 ){
// 比较 num1 和 num2 中当前的元素大小
// 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
// 为了防止越界 i 必须是大于等于 0
if( i >=0 && nums1[i] > nums2[j] ){
// 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
// 此时 cur 的元素已经确定下来
nums1[cur] = nums1[i];
// 接下来去确定 cur 前面一个元素应该放什么数字
cur--;
// 此时，索引 i 需要向前移动
i--;
// 否则，如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
}else{
// 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
nums1[cur] = nums2[j];
// 接下来去确定 cur 前面一个元素应该放什么数字
cur--;
// 此时，索引 j 需要向前移动
j--;
}
}
}
};3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https:#www.algomooc.com/555.html
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 合并两个有序数组( LeetCode 88 ):https:#leetcode-cn.com/problems/merge-sorted-array/
class Solution :
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# 索引从有序数组 nums1 有效元素的末端开始
# 数组的下标索引从零开始计数
# 索引 0 1 2
# 数组 [ 1 , 2 , 3 ]
i = m - 1
# 索引从有序数组 nums2 的末端开始
j = n - 1
# 从有序数组 nums1 最末端的位置开始保存元素
cur = m + n - 1
# 通过循环把 num2 的元素都移动到 num1 中
while j >= 0 :
# 比较 num1 和 num2 中当前的元素大小
# 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
# 为了防止越界 i 必须是大于等于 0
if i >=0 and nums1[i] > nums2[j]:
# 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
# 此时 cur 的元素已经确定下来
nums1[cur] = nums1[i]
# 接下来去确定 cur 前面一个元素应该放什么数字
cur-=1
# 此时，索引 i 需要向前移动
i-=1
# 否则，如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
else:
# 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
nums1[cur] = nums2[j]
# 接下来去确定 cur 前面一个元素应该放什么数字
cur-=1
# 此时，索引 j 需要向前移动
j-=1# 题目：LC88. 合并两个有序数组
# 难度：简单
# 作者：许老师-闭着眼睛学数理化
# 算法：双指针
# 代码看不懂的地方，请直接在群上提问
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# i是nums1的下标（不包含0的部分）
# j是nums2的下标
i = m - 1
j = n - 1
# cur是nums1的下标（包含最后的0的部分）
cur = m + n - 1
# 我们需要把所有nums2中的值放到nums1中，故要求j >= 0
# 当j == -1时，说明nums2中所有的元素均已经放到nums1中了
# 此时可以退出循环
while j >= 0:
# 如果i < 0，说明nums1中的值已经用完
# 把nums2[j]放到nums1[cur]，cur和j均递减
if i < 0:
nums1[cur] = nums2[j]
cur -= 1
j -= 1
# i >= 0的情况，nums1中的值还没有用完
else:
# nums1[i]大于等于nums2[j]，nums1[i]要放到nums1[cur]
# 然后cur和i均递减
if nums1[i] >= nums2[j]:
nums1[cur] = nums1[i]
cur -= 1
i -= 1
# nums1[i]小于nums2[j]，nums2[j]要放到nums1[cur]
# 然后cur和j均递减
# 以下内容可以合并到i < 0的情况，即变成吴师兄的代码
else:
nums1[cur] = nums2[j]
cur -= 1
j -= 1
四、复杂度分析
时间复杂度：O(m+n)。指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
空间复杂度：O(m+n)。