排序算法之：合并两个已排序数组的高效算法——双指针法与空间优化策略
字数 2779 2025-12-23 06:28:08

排序算法之：合并两个已排序数组的高效算法——双指针法与空间优化策略

1. 问题描述

我们面临一个经典的排序相关任务：给定两个 已排序的非递减整数数组 nums1 和 nums2，以及两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数量。

已知：

  • nums1 的长度为 m + n，其中前 m 个元素是已经排好序的有效元素，后 n 个位置（初始值通常是0或任意值）被预留出来，用于容纳合并后的所有元素。
  • nums2 的长度为 n，包含了 n 个已排序的有效元素。

目标：将 nums2 合并到 nums1 中，使合并后的 nums1 数组整体保持非递减顺序。最终结果就存储在 nums1 中，不允许使用额外的、与问题规模成比例的空间（即要求原地修改 nums1）。

示例:
输入：
nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3
输出：
nums1 = [1, 2, 2, 3, 5, 6]

核心约束：必须在不使用另一个大小为 m+n 的数组的前提下，完成合并。

2. 解题思路演进

第一步：直观但低效的方法

最直接的想法可能是：将 nums2 的所有元素先直接放入 nums1 末尾预留的 n 个位置，然后对整个 nums1（长度为 m+n）调用标准排序算法（如快速排序）。

  • 缺点：这种方法没有利用 nums1 和 nums2 已经各自有序 这个关键信息。排序整个数组的时间复杂度为 O((m+n) log(m+n))，不够高效。空间复杂度虽然也是 O(1)（原地排序），但存在更优解。

第二步：利用额外空间的简单归并

标准的归并排序（Merge）操作思路是：创建一个大小为 m+n 的临时数组 temp。使用三个指针 i、j、k：

  • i 初始指向 nums1 的第一个有效元素（索引 0）。
  • j 初始指向 nums2 的第一个元素（索引 0）。
  • k 初始指向 temp 的第一个位置（索引 0）。
    然后，比较 nums1[i] 和 nums2[j]，将较小的那个放入 temp[k]，并移动相应的指针。重复此过程直到其中一个数组遍历完，再将另一个数组剩余的部分直接复制到 temp 末尾。最后将 temp 的内容复制回 nums1。
  • 优点：时间复杂度是完美的 O(m+n)，因为我们只遍历了每个数组一次。
  • 缺点：空间复杂度是 O(m+n)，因为需要额外的 temp 数组。这不符合题目对“原地”的隐含要求（尽管题目可能没有明确禁止，但追求最优解时这是需要优化的）。

第三步：关键洞察——逆向双指针法（从后向前填充）

我们注意到 nums1 的后面有 n 个预留的、可以覆盖的位置。如果我们还是从前往后比较和填充，在将 nums1 的元素放入正确位置时，可能会覆盖掉后面尚未比较的 nums1 元素，导致信息丢失。

核心策略逆转：既然后面有空位，且两个数组的最大值最终一定在最后的位置，我们何不从后往前（从大到小）进行归并呢？

算法步骤详解：

  1. 指针初始化：

    • p1：指向 nums1 的最后一个有效元素，即索引 m-1 处。
    • p2：指向 nums2 的最后一个元素，即索引 n-1 处。
    • p：指向 nums1 数组的最后一个位置，即索引 m+n-1 处。这个位置是我们当前要填充的目标位置。

  2. 逆向归并循环：

    • 只要 p1 >= 0 且 p2 >= 0，说明两个数组都还有元素未处理，就执行循环：
      • 比较 nums1[p1] 和 nums2[p2]。
      • 将两者中 较大 的值，放入 nums1[p]。
      • 将较大值所属数组的指针（p1 或 p2）向前移动一位（减1）。
      • 将目标位置指针 p 向前移动一位（减1）。

  3. 处理剩余元素：

    • 循环结束后，有两种情况：
      • 情况 A：p2 >= 0，这意味着 nums2 中还剩一些元素（这些元素是所有剩余元素中最小的），而 nums1 中的有效元素已经全部正确归位。此时，我们只需要把 nums2 中剩下的这些元素（从索引0到 p2）按顺序复制到 nums1 的前 p2+1 个位置即可。
      • 情况 B：p1 >= 0，这意味着 nums2 的所有元素已经处理完，而 nums1 中剩余的元素本来就在正确的位置（因为我们是原地从后往前放），所以什么都不用做。

为什么这个方法正确且高效？

  • 正确性：我们总是比较两个数组中当前未处理的、各自最大的元素，将其中最大的放到当前未填充的最末尾位置。这保证了从后往前，nums1 被逐步填充为正确的非递减序列。
  • 时间复杂度：O(m+n)。每个元素只被比较和移动一次。
  • 空间复杂度：O(1)。只使用了几个指针变量，没有使用与 m 或 n 成比例的额外空间。

3. 算法流程示例

以示例说明：
初始状态：
nums1 = [1, 2, 3, 0, 0, 0]， p1=2 (指向3)， p2=2 (指向6)， p=5

循环步骤：
Step1: nums1[p1]=3, nums2[p2]=6, 6更大 -> nums1[5]=6, p2=1, p=4 -> [1,2,3,0,0,6]
Step2: nums1[p1]=3, nums2[p2]=5, 5更大 -> nums1[4]=5, p2=0, p=3 -> [1,2,3,0,5,6]
Step3: nums1[p1]=3, nums2[p2]=2, 3更大 -> nums1[3]=3, p1=1, p=2 -> [1,2,3,3,5,6]
Step4: nums1[p1]=2, nums2[p2]=2, 相等 (取nums2的也行) -> nums1[2]=2, p2=-1, p=1 -> [1,2,2,3,5,6]

循环结束，因为 p2 变为 -1 (p2 < 0)，所以 nums2 已处理完，算法结束。
最终结果为 [1, 2, 2, 3, 5, 6]。

4. 边界条件与实现细节

  • 空数组处理：如果 m=0，则 nums1 的有效部分为空。算法中 p1 初始为 -1，进入循环后第一个判断 p1>=0 为假，循环直接跳过。随后判断 p2>=0 为真，会将整个 nums2 复制到 nums1 开头，完全正确。
  • 指针范围：需要确保指针在操作数组时不越界。我们的初始化 p1=m-1, p2=n-1, p=m+n-1 在逻辑上是严谨的。在复制剩余元素时，源和目标索引的计算要小心。
  • 稳定性：对于相等元素 (nums1[p1] == nums2[p2])，优先放哪一个（移动 p1 还是 p2）在排序结果上是等价的，不影响非递减顺序。但从“稳定排序”的角度（如果元素附带其他信息），通常优先移动 nums1 的指针（即先放 nums1 的元素）可以保持 nums1 内部原有相等元素的相对顺序，但题目未要求，此处可自由选择。

这个逆向双指针归并法是解决该问题的标准且最优解，它巧妙地利用了输入数组的特性，实现了时间复杂度和空间复杂度的最优平衡。

排序算法之：合并两个已排序数组的高效算法——双指针法与空间优化策略 1. 问题描述 我们面临一个经典的排序相关任务：给定两个 已排序的非递减整数数组 nums1 和 nums2 ，以及两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数量。 已知： nums1 的长度为 m + n ，其中前 m 个元素是已经排好序的有效元素，后 n 个位置（初始值通常是0或任意值）被预留出来，用于容纳合并后的所有元素。 nums2 的长度为 n ，包含了 n 个已排序的有效元素。 目标 ：将 nums2 合并到 nums1 中，使合并后的 nums1 数组整体保持 非递减顺序 。最终结果就存储在 nums1 中，不允许使用额外的、与问题规模成比例的空间（即要求原地修改 nums1 ）。 示例 : 输入： nums1 = [ 1, 2, 3, 0, 0, 0 ], m = 3 nums2 = [ 2, 5, 6 ], n = 3 输出： nums1 = [ 1, 2, 2, 3, 5, 6 ] 核心约束 ：必须在不使用另一个大小为 m+n 的数组的前提下，完成合并。 2. 解题思路演进 第一步：直观但低效的方法 最直接的想法可能是：将 nums2 的所有元素先直接放入 nums1 末尾预留的 n 个位置，然后对整个 nums1 （长度为 m+n ）调用标准排序算法（如快速排序）。 缺点 ：这种方法没有利用 nums1 和 nums2 已经各自有序 这个关键信息。排序整个数组的时间复杂度为 O((m+n) log(m+n))，不够高效。空间复杂度虽然也是 O(1)（原地排序），但存在更优解。 第二步：利用额外空间的简单归并 标准的归并排序（Merge）操作思路是：创建一个大小为 m+n 的临时数组 temp 。使用三个指针 i 、 j 、 k ： i 初始指向 nums1 的第一个有效元素（索引 0）。 j 初始指向 nums2 的第一个元素（索引 0）。 k 初始指向 temp 的第一个位置（索引 0）。 然后，比较 nums1[i] 和 nums2[j] ，将较小的那个放入 temp[k] ，并移动相应的指针。重复此过程直到其中一个数组遍历完，再将另一个数组剩余的部分直接复制到 temp 末尾。最后将 temp 的内容复制回 nums1 。 优点 ：时间复杂度是完美的 O(m+n) ，因为我们只遍历了每个数组一次。 缺点 ：空间复杂度是 O(m+n) ，因为需要额外的 temp 数组。这不符合题目对“原地”的隐含要求（尽管题目可能没有明确禁止，但追求最优解时这是需要优化的）。 第三步：关键洞察——逆向双指针法（从后向前填充） 我们注意到 nums1 的后面有 n 个预留的、可以覆盖的位置。如果我们还是 从前往后 比较和填充，在将 nums1 的元素放入正确位置时，可能会覆盖掉后面尚未比较的 nums1 元素，导致信息丢失。 核心策略逆转 ：既然后面有空位，且两个数组的 最大值 最终一定在最后的位置，我们何不从后往前（从大到小）进行归并呢？ 算法步骤详解 ： 指针初始化 ： p1 ：指向 nums1 的最后一个 有效元素 ，即索引 m-1 处。 p2 ：指向 nums2 的最后一个元素，即索引 n-1 处。 p ：指向 nums1 数组的最后一个位置，即索引 m+n-1 处。这个位置是我们当前要填充的目标位置。 逆向归并循环 ： 只要 p1 >= 0 且 p2 >= 0 ，说明两个数组都还有元素未处理，就执行循环： 比较 nums1[p1] 和 nums2[p2] 。 将两者中 较大 的值，放入 nums1[p] 。 将较大值所属数组的指针（ p1 或 p2 ）向前移动一位（减1）。 将目标位置指针 p 向前移动一位（减1）。 处理剩余元素 ： 循环结束后，有两种情况： 情况 A： p2 >= 0 ，这意味着 nums2 中还剩一些元素（这些元素是所有剩余元素中最小的），而 nums1 中的有效元素已经全部正确归位。此时，我们只需要把 nums2 中剩下的这些元素（从索引0到 p2 ）按顺序复制到 nums1 的前 p2+1 个位置即可。 情况 B： p1 >= 0 ，这意味着 nums2 的所有元素已经处理完，而 nums1 中剩余的元素本来就在正确的位置（因为我们是原地从后往前放），所以什么都不用做。 为什么这个方法正确且高效？ 正确性 ：我们总是比较两个数组中当前未处理的、各自最大的元素，将其中最大的放到当前未填充的最末尾位置。这保证了从后往前， nums1 被逐步填充为正确的非递减序列。 时间复杂度 ： O(m+n) 。每个元素只被比较和移动一次。 空间复杂度 ： O(1) 。只使用了几个指针变量，没有使用与 m 或 n 成比例的额外空间。 3. 算法流程示例 以示例说明： 初始状态： nums1 = [ 1, 2, 3, 0, 0, 0 ]， p1=2 (指向3)， p2=2 (指向6)， p=5 循环结束，因为 p2 变为 -1 ( p2 < 0 )，所以 nums2 已处理完，算法结束。 最终结果为 [1, 2, 2, 3, 5, 6] 。 4. 边界条件与实现细节 空数组处理 ：如果 m=0 ，则 nums1 的有效部分为空。算法中 p1 初始为 -1，进入循环后第一个判断 p1>=0 为假，循环直接跳过。随后判断 p2>=0 为真，会将整个 nums2 复制到 nums1 开头，完全正确。 指针范围 ：需要确保指针在操作数组时不越界。我们的初始化 p1=m-1 , p2=n-1 , p=m+n-1 在逻辑上是严谨的。在复制剩余元素时，源和目标索引的计算要小心。 稳定性 ：对于相等元素 ( nums1[p1] == nums2[p2] )，优先放哪一个（移动 p1 还是 p2 ）在排序结果上是等价的，不影响非递减顺序。但从“稳定排序”的角度（如果元素附带其他信息），通常优先移动 nums1 的指针（即先放 nums1 的元素）可以保持 nums1 内部原有相等元素的相对顺序，但题目未要求，此处可自由选择。 这个 逆向双指针归并法 是解决该问题的标准且最优解，它巧妙地利用了输入数组的特性，实现了时间复杂度和空间复杂度的最优平衡。