网站导航栏怎么设置,韩国女足还能出线吗,wordpress问题解决,如何给公司注册网站力扣88题#xff1a;合并两个有序数组
题目描述
给定两个按非递减顺序排列的整数数组 nums1 和 nums2#xff0c;以及它们的长度 m 和 n#xff0c;要求将 nums2 合并到 nums1#xff0c;使得合并后的数组仍按非递减顺序排列。
输入与输出
示例 1#xff1a;
输入合并两个有序数组
题目描述
给定两个按非递减顺序排列的整数数组 nums1 和 nums2以及它们的长度 m 和 n要求将 nums2 合并到 nums1使得合并后的数组仍按非递减顺序排列。
输入与输出
示例 1
输入nums1 [1,2,3,0,0,0], m 3nums2 [2,5,6], n 3
输出[1,2,2,3,5,6]示例 2
输入nums1 [1], m 1nums2 [], n 0
输出[1]示例 3
输入nums1 [0], m 0nums2 [1], n 1
输出[1]算法思路
1. 问题分析
题目要求我们原地合并两个数组
nums1 的后半部分预留了足够的空间大小为 m n m n mn。nums1 和 nums2 已经是有序的。
2. 双指针逆向合并
我们从两个数组的尾部开始比较选择较大的元素放入 nums1 的末尾。具体步骤如下
2.1 初始化指针
定义指针 p1指向 nums1 的有效元素的末尾即索引 m − 1 m - 1 m−1。定义指针 p2指向 nums2 的末尾即索引 n − 1 n - 1 n−1。定义指针 p指向 nums1 的总末尾即索引 m n − 1 m n - 1 mn−1。
2.2 比较与插入
如果 nums1[p1] nums2[p2]将 nums1[p1] 放入 nums1[p]并移动 p1 和 p。如果 nums1[p1] nums2[p2]将 nums2[p2] 放入 nums1[p]并移动 p2 和 p。
2.3 拷贝剩余元素
如果 nums2 中还有未处理的元素直接将它们拷贝到 nums1 的前面。如果 nums1 中还有未处理的元素则无需额外操作。
2.4 循环终止条件
当 p1 0 且 p2 0 时循环结束。 代码实现
以下是修正后的完整代码
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int i nums1Size - 1; // 从 nums1 的尾部开始填充while (m 0 || n 0) {if (n 0 (m 0 || nums1[m - 1] nums2[n - 1])) {nums1[i--] nums2[--n];} else {nums1[i--] nums1[--m];}}
}代码详解
1. 初始化指针
定义三个指针
p1 m - 1指向 nums1 有效部分的末尾。p2 n - 1指向 nums2 的末尾。p m n - 1指向 nums1 的尾部。
2. 从尾部向前合并
通过比较 nums1[p1] 和 nums2[p2]将较大的元素放入 nums1[p]并更新指针。以下是操作逻辑
if (n 0 (m 0 || nums1[m - 1] nums2[n - 1])) {nums1[p--] nums2[--n];
} else {nums1[p--] nums1[--m];
}3. 拷贝剩余的 nums2
如果 nums2 中还有未处理的元素直接拷贝
while (n 0) {nums1[p--] nums2[--n];
}复杂度分析
时间复杂度
遍历数组时每次比较、移动只需 O ( 1 ) O(1) O(1) 时间总体复杂度为 O ( m n ) O(m n) O(mn)。
空间复杂度
使用了常量级的额外空间复杂度为 O ( 1 ) O(1) O(1)。 测试用例
测试用例 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]测试用例 3
输入
nums1 [0], m 0
nums2 [1], n 1输出
[1]测试用例 4
输入
nums1 [2,2,2,0,0,0], m 3
nums2 [2,2,2], n 3输出
[2,2,2,2,2,2]
