合并两个有序数组
示例 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 中。
逆向双指针代码：
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m-1,p2 = n-1;int tail = m+n-1;int cur;while(p1>=0 || p2>=0){if(p1==-1){cur = nums2[p2--];}else if(p2==-1){cur = nums1[p1--];}else if(nums1[p1]>nums2[p2]){cur = nums1[p1--];}else if(nums1[p1]<nums2[p2]){cur = nums2[p2--];}else{cur = nums1[p1--];}nums1[tail--]=cur;}}
}
GPT的思路
国内使用地址：点我跳转
我们可以使用双指针法从后向前遍历，避免将已经排序的数组打乱。这个方法的核心思路是从 nums1 的末尾开始填充较大的元素，因为末尾是用零填充的空闲区域，这样我们可以避免覆盖 nums1 的有效元素。
以下是实现的步骤：
- 定义两个指针，分别指向
nums1和nums2有效元素的末尾。 - 比较两个数组中的当前元素，将较大的元素放到
nums1的末尾。 - 移动相应的指针，继续填充剩余的元素。
- 如果
nums2中还有剩余元素没有处理完（即nums1中的元素已经全部处理完），就直接将nums2的元素放入nums1。
下面是 Java 代码的实现：
public class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {// 初始化三个指针，分别指向 nums1 和 nums2 的末尾，以及合并后数组的末尾int p1 = m - 1;int p2 = n - 1;int p = m + n - 1;// 从后往前遍历，比较 nums1 和 nums2 的元素while (p1 >= 0 && p2 >= 0) {if (nums1[p1] > nums2[p2]) {nums1[p] = nums1[p1];p1--;} else {nums1[p] = nums2[p2];p2--;}p--;}// 如果 nums2 还有剩余元素，直接填入 nums1while (p2 >= 0) {nums1[p] = nums2[p2];p--;p2--;}}
}
详细解释：
-
指针的初始化：
p1指向nums1中最后一个有效元素，即m - 1。p2指向nums2中最后一个元素，即n - 1。p指向nums1中最后一个位置，即m + n - 1。
-
比较元素并填充：
- 在
p1和p2都没有越界的情况下，比较nums1[p1]和nums2[p2]，将较大的元素放在nums1[p]位置。 - 然后移动相应的指针，继续比较下一个元素。
- 在
-
处理剩余的元素：
- 如果
nums2中还有元素未处理完，直接将它们放入nums1对应的位置。 - 如果
nums1的元素已经放完，但nums2还有剩余的元素，这种情况是可以通过后续的while (p2 >= 0)循环来处理。
- 如果
示例解释：
- 对于示例1：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
- 初始状态：
p1 = 2, p2 = 2, p = 5 - 比较
nums1[2] = 3和nums2[2] = 6，6 大，放入nums1[5]，指针移动：p2 = 1, p = 4 - 比较
nums1[2] = 3和nums2[1] = 5，5 大，放入nums1[4]，指针移动：p2 = 0, p = 3 - 比较
nums1[2] = 3和nums2[0] = 2，3 大，放入nums1[3]，指针移动：p1 = 1, p = 2 - 比较
nums1[1] = 2和nums2[0] = 2，相等，放入nums1[2]，指针移动：p2 = -1, p = 1 - 此时
p2 < 0，合并完成，最终结果为[1, 2, 2, 3, 5, 6]。
时间复杂度分析：
- 由于每个元素只遍历一次，时间复杂度为 O(m + n)。
- 空间复杂度为 O(1)，因为我们只是在原地修改
nums1。
这个方法能够高效地解决问题，并且符合进阶要求的 O(m + n) 复杂度。
