leetcode88. 合并两个有序数组，倒着做

leetcode88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

题目分析

我们需要合并两个有序数组 nums1 和 nums2，其中 nums1 的长度足够容纳 nums1 和 nums2 的所有元素。合并后的数组应该是递减有序的。我们可以从数组的末尾开始合并，这样可以避免覆盖 nums1 中的元素。

总体思维导图

算法步骤

1. 初始化三个指针：pos 指向 nums1 和 nums2 合并后的末尾，m 指向 nums1 的末尾，n 指向 nums2 的末尾。
2. 当 m 和 n 都大于 0 时，执行以下步骤：
   • 如果 n 为 0 或者 nums1[m-1] 大于等于 nums2[n-1]，将 nums1[m-1] 放入 nums1[pos]，然后 m 和 pos 分别减 1。
   • 否则，将 nums2[n-1] 放入 nums1[pos]，然后 n 和 pos 分别减 1。
3. 如果 n 大于 0，将 nums2 中的剩余元素复制到 nums1 的开头。

流程图

算法流程图

具体代码（C++/Go）

class Solution {
public:
//倒着做void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int pos=m+n-1;while(m>0 || n>0){if(n==0||(m!=0 && nums1[m-1]>=nums2[n-1])){nums1[pos]=nums1[m-1];pos--;m--;}else{nums1[pos]=nums2[n-1];pos--;n--;}}}
}; 

func merge(nums1 []int, m int, nums2 []int, n int) {pos := m + n - 1for m > 0 || n > 0 {if n == 0 || (m!= 0 && nums1[m-1] >= nums2[n-1]) {nums1[pos] = nums1[m-1]pos--m--} else {nums1[pos] = nums2[n-1]pos--n--}}
}

算法分析

• 时间复杂度：O(m + n)
• 空间复杂度：O(1)
• 易错点：注意指针的移动和边界条件。
• 注意事项：确保 nums1 的长度足够容纳 nums1 和 nums2 的所有元素。

相似题目

题目	链接
合并两个有序链表	https://leetcode.cn/problems/merge-two-sorted-lists/
合并K个升序链表	https://leetcode.cn/problems/merge-k-sorted-lists/
间隔合并两个数组	https://leetcode.cn/problems/interval-list-intersections/