LeetCode 88. Merge Sorted Array 题解题目描述给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。注意最终合并后数组不应由函数返回而是存储在数组nums1中。为了应对这种情况nums1的初始长度为m n其中前m个元素表示应保留的元素后n个元素为 0 应忽略。nums2的长度为n。示例 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 中。解题思路方法双指针从后向前思路使用三个指针p1指向nums1的末尾有效元素的最后一个位置p2指向nums2的末尾p指向nums1的最终末尾合并后的最后一个位置从后向前遍历两个数组比较nums1[p1]和nums2[p2]的大小如果nums1[p1] nums2[p2]将nums1[p1]放到nums1[p]的位置p1和p都向左移动一位否则将nums2[p2]放到nums1[p]的位置p2和p都向左移动一位当p2小于 0 时说明nums2已经全部合并到nums1中结束循环当p1小于 0 时说明nums1的有效元素已经全部处理完毕将nums2中剩余的元素全部复制到nums1中复杂度分析时间复杂度O(m n)其中 m 和 n 分别是两个数组的长度。需要遍历两个数组一次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法双指针从后向前class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: Do not return anything, modify nums1 in-place instead. # 初始化三个指针 p1 m - 1 # nums1 的有效元素的最后一个位置 p2 n - 1 # nums2 的最后一个位置 p m n - 1 # nums1 的最终末尾位置 # 从后向前遍历两个数组 while p1 0 and p2 0: if nums1[p1] nums2[p2]: nums1[p] nums1[p1] p1 - 1 else: nums1[p] nums2[p2] p2 - 1 p - 1 # 如果 nums2 还有剩余元素全部复制到 nums1 中 while p2 0: nums1[p] nums2[p2] p2 - 1 p - 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 [4,5,6,0,0,0], m 3, nums2 [1,2,3], n 3输出[1,2,3,4,5,6]总结本题是一个经典的合并有序数组问题主要考察对双指针技巧的理解和使用。通过使用双指针从后向前遍历我们可以在不使用额外空间的情况下高效地合并两个有序数组。双指针的核心思想是从两个数组的末尾开始比较元素将较大的元素放到合并后数组的末尾然后向前移动指针。这样可以避免覆盖nums1中的有效元素从而实现原地合并。这种方法不仅适用于合并两个有序数组问题还可以应用于许多其他需要合并有序数据的场景。掌握双指针的使用对于解决这类问题非常重要。