LeetCode 88：合并两个有序数组 | 双指针从后向前求解

LeetCode 88合并两个有序数组 | 双指针从后向前求解引言合并两个有序数组Merge Sorted Array是 LeetCode 第 88 题难度为 Easy但却是双指针法应用的经典案例。题目要求将两个已排序的数组 nums1 和 nums2 合并到 nums1 中假设 nums1 有足够的空间mn来存储 nums2 中的元素。这个问题的关键在于如何在不使用额外数组的情况下原地合并两个已排序的数组。表面上看这道题似乎很简单但如何在原地即不使用额外数组的情况下高效合并两个数组需要一定的技巧。如果从前往后比较并移动元素之前的元素可能被覆盖导致数据丢失。因此从后往前合并是解决这个问题的关键思路这个技巧在实际工程中也有广泛应用。问题分析题目描述给定两个有序整数数组 nums1 和 nums2将 nums2 合并到 nums1 中使 nums1 成为一个有序数组。假设 nums1 有足够的空间大小为 m n来存储 nums2 中的额外元素nums1 和 nums2 的初始长度分别为 m 和 n。例如输入 nums1 [1,2,3,0,0,0]m 3nums2 [2,5,6]n 3合并后 nums1 变为 [1,2,2,3,5,6]。问题特点这个问题的关键特点在于原地修改的要求。nums1 的初始长度 mn预留了 n 个位置来存放 nums2 的元素。这意味着我们可以从 nums1 的末尾开始填充结果避免覆盖还未处理的元素。这个观察启发了从后往前的双指针解法。如果采用从前往后的方式当我们把 nums2 的元素复制到 nums1 的开头时可能会覆盖 nums1 中还未处理的元素。虽然可以使用临时数组来避免这个问题但题目要求原地修改。双指针从后往前的技巧正是解决这类问题的标准方法。边界情况有几个重要的边界情况需要考虑。当 nums2 为空时不需要任何操作。当 nums1 的有效部分为空时需要将 nums2 的所有元素复制到 nums1 的开头。还有一种情况是两个数组中可能存在相等的元素这时的合并顺序不影响正确性只需要保证最终结果是有序的。算法设计从后往前的双指针def merge(nums1, m, nums2, n): p1 m - 1 p2 n - 1 p m n - 1 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 if p2 0: nums1[:p2 1] nums2[:p2 1]这段代码展示了从后往前的双指针合并算法。三个指针分别指向p1 指向 nums1 当前处理的最后一个有效元素位置 m-1p2 指向 nums2 的最后一个元素位置 n-1p 指向 nums1 当前位置位置 mn-1。每次比较 nums1[p1] 和 nums2[p2]将较大的元素放到 nums1[p] 位置然后将对应的指针左移。当其中一个数组处理完毕后可能还有另一个数组的剩余元素需要复制。如果 nums2 还有剩余直接将它们复制到 nums1 的开头即可因为此时 p2 之后的位置已经全部处理完毕。注意当 nums1 还有剩余时由于它们已经在正确的位置不需要额外操作。算法正确性证明为什么这个算法是正确的关键在于从后往前处理时的保证。在第 p 个位置填充元素时位置 p 之后的所有位置都已经是最终值不会再被修改。同时p1 指向 nums1 中还未处理的最大元素p2 指向 nums2 中还未处理的最大元素因此比较这两个元素并将较大者放到位置 p 是正确的选择。通过数学归纳法可以严格证明算法的正确性。假设当处理到位置 p 时p1 到 mn-1 的位置都已经是正确的值。我们需要证明此时 nums1[p] 的值也是正确的。由于 nums1[p1] 是 nums1 中所有未处理元素的最大值nums2[p2] 是 nums2 中所有未处理元素的最大值两者中的较大者就是所有未处理元素的最大值应该放在位置 p。因此算法是正确的。复杂度分析时间复杂度合并操作的时间复杂度为 O(mn)。每个元素最多被处理两次一次比较可能一次赋值因此总操作次数与两个数组的长度之和成正比。不考虑初始的 m 和 n 的赋值操作主要的比较和赋值循环是线性的。空间复杂度算法的空间复杂度为 O(1)只使用了常数个指针变量。无论输入数组有多大额外的内存使用始终是常数级别的。这个空间效率是题目要求原地修改的基础。代码实现细节Python 实现def merge(nums1, m, nums2, n): p1, p2 m - 1, n - 1 tail m n - 1 while p1 0 and p2 0: if nums1[p1] nums2[p2]: nums1[tail] nums1[p1] p1 - 1 else: nums1[tail] nums2[p2] p2 - 1 tail - 1 if p2 0: nums1[:p2 1] nums2[:p2 1]注意这里使用而不是来处理相等的情况这使得 nums1 的元素优先被放置保持了算法的稳定性虽然在这个特定问题中稳定性不是必须的。Java 实现public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 m - 1; int p2 n - 1; int tail m n - 1; while (p1 0 p2 0) { if (nums1[p1] nums2[p2]) { nums1[tail] nums1[p1]; p1--; } else { nums1[tail] nums2[p2]; p2--; } tail--; } for (int i 0; i p2; i) { nums1[i] nums2[i]; } }Java 实现中最后需要将 nums2 的剩余元素复制到 nums1 的开头。这是因为如果 nums2 还有剩余它们肯定比 nums1 中任何剩余元素都小因为 nums1 处理完毕意味着 p1 0需要放在最前面。变种问题合并K个有序数组合并 K 个有序数组是合并两个有序数组的自然扩展。最简单的方法是使用最小堆维护一个大小为 K 的最小堆每次取出堆顶元素当前最小的然后将该元素所在数组的下一个元素加入堆中。这种方法的时间复杂度为 O(N log K)其中 N 是所有元素的总数。另一种方法是两两合并先合并数组 1 和 2然后将结果与数组 3 合并以此类推。这种方法实现简单但时间复杂度较高为 O(KN)。合并两个有序链表合并两个有序链表与合并两个有序数组非常相似也可以使用双指针法。区别在于链表节点不能随机访问需要通过 next 指针遍历。由于链表节点不能原地修改不能像数组那样直接赋值通常需要创建新的链表来存储结果。扩展哨兵节点在合并有序链表的问题中使用哨兵节点dummy node可以简化代码。哨兵节点是一个临时节点作为合并后链表的头节点它不存储实际数据。使用哨兵节点可以避免处理空链表等边界情况使代码更加简洁。测试用例def test_merge(): nums1 [1, 2, 3, 0, 0, 0] merge(nums1, 3, [2, 5, 6], 3) assert nums1 [1, 2, 2, 3, 5, 6] nums2 [1] merge(nums2, 1, [], 0) assert nums2 [1] nums3 [0] merge(nums3, 0, [1], 1) assert nums3 [1] nums4 [2, 0] merge(nums4, 1, [1], 1) assert nums4 [1, 2] nums5 [4, 5, 6, 0, 0, 0] merge(nums5, 3, [1, 2, 3], 3) assert nums5 [1, 2, 3, 4, 5, 6] print(所有测试用例通过)实际应用场景合并有序数组/链表是外部排序算法的基础。在外部排序中数据量太大无法全部放入内存需要分块排序后合并。合并 K 个有序数组的算法正是外部排序中多路归并的核心技术。在数据库系统中当执行 ORDER BY 和 LIMIT 操作时如果数据无法完全在内存中排序也会用到多路归并的技术。此外在归并排序的合并阶段本质上也是在合并两个有序子序列。在实时数据流处理中如果需要合并多个有序的数据流双指针法同样适用。只要数据流是有序的就可以使用类似的合并策略来产生合并后的有序输出。总结合并两个有序数组是一个看似简单但蕴含重要算法思想的经典问题。从后往前的双指针技巧不仅解决了原地合并的问题还展示了在数组操作中如何避免数据覆盖的风险。这个技巧在许多类似问题中都有应用是算法学习中必须掌握的基础技能。通过本文的分析希望读者能够深入理解双指针法在有序数组问题中的应用并将其推广到更多类似的算法问题中。合并有序序列的思路是许多复杂算法的基础掌握这些基础技巧对于提升整体算法能力至关重要。