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 - 1
    for 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/

原文地址：https://blog.csdn.net/qq_51350957/article/details/145221877

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！