DSA 中的无额外空间合并问题

合并两个已排序数组是在计算机科学中一项流行的操作。当被要求在不分配额外空间的情况下就地组合这些数组时，难度就出现了。这个问题经常出现在内存是关键限制的面试和实际场景中。让我们看看解决“无额外空间合并”问题的几种方法。

理解问题

考虑两个已排序的数组，比如 A 和 B，它们按升序排列。目的是将这两个数组合并成一个已排序的数组，通常称为数组 C，而不使用任何额外的空间。问题在于如何在不分配新内存或不依赖辅助数据结构（如数组、列表或其他集合）的情况下做到这一点。

方法 1：朴素解决方案

“无额外空间合并”问题的朴素解决方案采用了一种直接的合并方法，而忽略了不使用额外空间的限制。这是一种简单的方法，您为合并后的结果分配额外的内存，并将两个数组的元素依次复制到这个新区域，同时保持排序顺序。

让我们逐步了解朴素方法

朴素方法的步骤

1. 内存分配

• 创建一个新数组，通常称为数组 C，其大小等于数组 A 和 B 的总和。

2. 迭代比较和合并

• 创建三个指针，分别指向数组 A、B 和合并数组 C。
• 同时开始遍历数组 A 和 B，比较当前指针处的元素。
• 在合并数组 C 中，复制数组 A 和 B 指针之间的较小元素。
• 向前移动数组 A/B 中的相关指针以及数组 C 中的指针。
• 重复此过程，直到数组 A 和 B 都为空。

3. 完成

• 当迭代完成，数组 C 中的所有元素都已合并后，该数组就成为已排序的合并数组。

复杂度分析

时间复杂度： O (n * m)，其中 'n' 和 'm' 是要合并的数组的大小。

空间复杂度： O (1)，表示算法就地操作，无需额外空间。

实施

输出

说明

1. 初始化变量

• 确定两个输入数组（arr1 和 arr2）的长度。
• 创建一个新数组 merged，该数组最初包含 arr1 的元素，并为 arr2 的元素留有额外空间。

2. 合并过程

• 将指针（merged_index、arr1_index 和 arr2_index）初始化在两个数组的末尾以及合并空间的末尾。
• 从末尾开始比较两个数组（arr1 和 arr2）中的元素。
• arr1[arr1_index] 和 arr2[arr2_index] 中较大的元素被放置在合并数组的末尾（merged[merged_index]）。
• 根据插入到合并数组中的元素相应地移动指针。

3. 完成

• 一旦两个数组都被遍历和合并，如果 arr2 中还有剩余元素，则将它们复制到合并数组中的相应位置。

4. 返回合并后的数组

• 该函数返回合并后的数组，该数组包含 arr1 和 arr2 的所有元素，按排序顺序排列，且除了用于合并的初始分配空间外，不使用任何额外空间。

方法 2（优化）：使用插入合并

“插入合并”优化策略用于就地组合两个已排序的数组，而无需占用任何额外空间。这种方法利用了两个数组都已排序的事实，可以快速组合它们，同时最大限度地减少不必要的运算。

让我们分解优化后的“插入合并”方法的各个阶段

步骤 1：初始化

• 考虑两个按升序排序的数组 A 和 B。数组 A 有 'm' 个元素（从 A[0] 到 A[m-1]），数组 B 有 'n' 个元素（从 B[0] 到 B[n-1]）。

步骤 2：比较合并

• 初始化两个指针，i 和 j。
• i 指向数组 A 的最后一个元素（i = m - 1）。
• j 指向数组 B 的开头（j = 0）。

步骤 3：合并操作

• 比较索引 A[i] 和 B[j] 处的元素。
• 如果索引 A[i] 处的元素大于索引 B[j] 处的元素
• 交换元素（A[i] 和 B[j]）。
• 将 i 减 1（在数组 A 中向左移动）。
• 将 j 加 1（在数组 B 中向右移动）。
• 继续此比较和交换，直到以下任一情况发生：
• i 小于 0（到达数组 A 的开头），或
• j 等于或大于 n（到达数组 B 的末尾）。

步骤 4：排序最终数组

• 在比较合并之后，某些元素可能需要放置在数组 A 和 B 中的正确位置。
• 分别对数组 A 和 B 进行排序，以确保所有元素都按正确的顺序排列。

步骤 5：合并数组

• 将数组 A 和 B 合并到 A 中，以获得最终的合并排序数组。这可以通过将数组 A 扩展到数组 B 的元素来实现。

复杂性分析

时间复杂度： 排序阶段是最重要的操作，由于对两个数组进行排序，因此时间复杂度为 O ((m + n) log (m + n))。

空间复杂度： 由于该方法在不分配额外空间的情况下执行所有操作，因此空间复杂度是常数（O(1)）。

实施

输出

说明

1. 比较合并

• 它首先比较 arr1 的最大元素（索引 m - 1 处）与 arr2 的最小元素（索引 0 处）。
• 如果 arr1 中的元素较大，则将其与 arr2 中较小的元素进行交换。
• 然后指针分别向 arr1 和 arr2 的中间移动，继续比较和必要时的交换。

2. 排序（可选）

• 最后对 arr1 和 arr2 进行排序，以确保它们的元素按升序排列。
• 如果两个数组已经排序，则此步骤可能不是必需的。

3. 合并数组

• 最后，它将已排序的 arr2 合并到已排序的 arr1 中，形成一个单一的已排序数组 arr1，其中包含来自两个数组的所有元素。

方法 3：间隙法（希尔排序变体）

间隙法，通常被认为是希尔排序的变体，它提供了一种有效的方法来合并两个已排序的数组，而不会消耗额外的空间。通过利用间隙或元素之间间隔的思想，这种技术优化了合并过程。

间隙就地合并算法方法

1. 计算间隙

• 通过取大于或等于数组 A 和 B 总大小的最小二的幂来计算间隙大小。
• 将确定的值设置为间隙的初始值。

2. 开始带间隙的合并

• 当间隙大于一时，开始遍历数组。
• 比较合并数组中相距“间隙”位置的元素。
• 如果数组 A 的元素大于数组 B 的元素（考虑间隙差），则交换元素。
• 继续以间隙为间隔比较和交换元素，直到到达数组的末尾。

3. 缩小间隙并重复

• 将间隙减半。
• 使用更新后的间隙重复比较和交换过程，直到间隙等于 1。

4. 间隙为 1 的传递

• 为了确保元素被正确放置，请使用插入排序等技术，以间隙为 1 对数组进行最后一次传递。
• 这个最后阶段可确保元素得到更精确的排序，从而得到完全排序的合并数组。

实施

输出

说明

1. 初始化

• n 和 m 分别代表数组 arr1 和 arr2 的长度。
• gap 变量最初设置为大于或等于两个数组总长度的最小二的幂。

2. 合并过程

带间隙的 while 循环

• 当 gap 值大于 0 时，代码执行迭代以合并数组。

合并步骤

• 代码以特定的间隙大小遍历两个数组并比较元素。
• 它开始比较同一数组中相距间隙位置的元素，并在需要时交换它们以保持排序顺序。
• 然后，它比较并交换两个数组之间的元素，确保它们在数组内的排序排列。

间隙调整

• 每次遍历数组后，gap 值都会减半，直到达到 1，这表示最后一次传递以确保元素的正确排列。

3. 返回合并后的数组

该函数返回修改后的 arr1 和 arr2，它们现在包含按排序顺序合并的元素，而无需使用任何额外空间。

4. 示例用法

• 示例用法演示了如何使用两个示例数组 array1 和 array2 来使用 merge_without_extra_space 函数。
• 将打印合并后的数组（result1 和 result2）作为输出。