优化数组重排：最小分组策略-java教程-PHP中文网

优化数组重排：最小分组策略

碧海醫心

发布： 2025-11-22 17:10:12

原创

458人浏览过

优化数组重排：最小分组策略

本文详细阐述了如何计算将一个具有唯一值的数组通过重新排列最少数量的连续子数组（分组）转换为另一个目标数组所需的最小分组数。通过构建目标数组的索引映射，并迭代检查源数组中元素的相对顺序，我们可以高效地识别出连续的、无需内部调整的片段，从而确定所需的最少分组数量。

理解数组分组与重排问题

在处理数组转换问题时，我们有时会遇到这样的场景：给定一个源数组 arr1 和一个目标数组 arr2，两者包含相同且唯一的元素，长度也一致。我们的目标是将 arr1 切割成最少数量的连续子数组（即“分组”），然后通过重新排列这些子数组，使其最终形态与 arr2 完全一致。问题的核心在于找到这个最小的分组数。

例如，考虑源数组 arr1 = [1, 4, 3, 2] 和目标数组 arr2 = [1, 2, 4, 3]。我们可以将 arr1 分割成 (1), (4, 3), (2) 这三个子数组。然后，通过重新排列这些子数组为 (1), (2), (4, 3)，我们就能得到 arr2。因此，对于这个例子，最小分组数是 3。

值得注意的是，一个简单的逐元素比较并计数不匹配项的方法是无效的。例如，对于 [1,4,3,2] 和 [1,2,4,3]，如果仅计算不匹配项，会发现 4!=2, 3!=4, 2!=3，得到 3 个不匹配，但这种方法无法反映出通过重排分组实现转换的本质，因为它没有考虑元素的相对位置和连续性。

核心算法思路

解决此类问题的关键在于利用数组中元素的唯一性。由于所有元素都是唯一的，每个元素在目标数组 arr2 中都有一个固定的、唯一的索引位置。我们可以通过构建一个映射（Map）来快速查询 arr2 中每个元素的值对应的索引。

算法的核心思想是遍历源数组 arr1，并追踪 arr1 中当前元素及其前一个元素在 arr2 中的相对位置。如果 arr1 中的当前元素在 arr2 中的索引恰好是其前一个元素在 arr2 中索引的“下一个”，那么这两个元素在 arr1 中形成的连续序列，在 arr2 中也是连续的，它们可以归为一个分组。反之，如果它们在 arr2 中的索引不连续，则意味着当前元素开启了一个新的分组。

详细步骤

构建索引映射： 创建一个 Map<Integer, Integer>，将目标数组 arr2 中的每个元素值作为键，其在 arr2 中的索引作为值。这个映射将允许我们以 O(1) 的时间复杂度查询任何元素在 arr2 中的目标位置。
初始化分组计数器： 初始化一个计数器 count 为 1。这是因为即使 arr1 和 arr2 完全相同，也至少需要一个分组（即整个数组本身）。
追踪前一个元素的索引： 获取 arr1 的第一个元素在 arr2 中的索引，并将其存储在 prevIndex 变量中。
遍历源数组 arr1： 从 arr1 的第二个元素开始，遍历直到数组结束。对于 arr1 中的每一个当前元素：
- 使用之前构建的索引映射，查找当前元素在 arr2 中的索引，并将其存储在 nextIndex 变量中。
- 判断是否属于同一分组： 比较 nextIndex 和 prevIndex + 1。
  - 如果 nextIndex == prevIndex + 1，这意味着当前元素在 arr2 中紧接着前一个元素。它们属于同一个逻辑分组。此时，更新 prevIndex = nextIndex，继续追踪。
  - 如果 nextIndex != prevIndex + 1，这意味着当前元素在 arr2 中的位置与前一个元素不连续。这表示我们遇到了一个新的分组的开始。此时，增加 count，并更新 prevIndex = nextIndex，以开始追踪这个新分组。
返回结果： 遍历结束后，count 的值即为所需的最小分组数。

示例演练

我们以 arr1 = [1, 4, 3, 2] 和 arr2 = [1, 2, 4, 3] 为例，逐步演示算法：

构建 arr2 的索引映射：indexByValue = {1:0, 2:1, 4:2, 3:3}

Smart Picture
Smart Picture 智能高效的图片处理工具

77

查看详情
初始化：count = 1prevIndex = indexByValue.get(arr1[0]) = indexByValue.get(1) = 0
遍历 arr1：
- i = 1 (元素 arr1[1] = 4)：nextIndex = indexByValue.get(4) = 2 比较 nextIndex (2) 和 prevIndex + 1 (0 + 1 = 1)。 2 != 1。不连续，说明 4 开启了一个新分组。 count 增加到 2。 prevIndex 更新为 nextIndex = 2。 当前分组：(1) 结束，新分组 (4) 开始
- i = 2 (元素 arr1[2] = 3)：nextIndex = indexByValue.get(3) = 3 比较 nextIndex (3) 和 prevIndex + 1 (2 + 1 = 3)。 3 == 3。连续，说明 3 属于当前分组。 prevIndex 更新为 nextIndex = 3。 当前分组：(4,3) 继续
- i = 3 (元素 arr1[3] = 2)：nextIndex = indexByValue.get(2) = 1 比较 nextIndex (1) 和 prevIndex + 1 (3 + 1 = 4)。 1 != 4。不连续，说明 2 开启了一个新分组。 count 增加到 3。 prevIndex 更新为 nextIndex = 1。 当前分组：(4,3) 结束，新分组 (2) 开始
遍历结束： 返回 count = 3。这与我们预期的结果一致。

代码实现

以下是使用 Java 语言实现上述算法的示例代码：

import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ArrayGroupingConverter {

    /**
     * 计算将 arr1 转换为 arr2 所需的最少分组数。
     * 两个数组包含唯一的整数值，且长度相同。
     *
     * @param arr1 源数组
     * @param arr2 目标数组
     * @return 最少分组数
     */
    public static int process(int[] arr1, int[] arr2) {
        // 1. 构建 arr2 中元素值到其索引的映射
        Map<Integer, Integer> indexByValue = mapIndices(arr2);

        // 2. 初始化分组计数器为 1 (至少有一个分组)
        int count = 1;

        // 3. 获取 arr1 第一个元素在 arr2 中的索引，作为 prevIndex
        int prevIndex = indexByValue.get(arr1[0]);

        // 4. 从 arr1 的第二个元素开始遍历
        for (int i = 1; i < arr1.length; i++) {
            // 获取当前元素在 arr2 中的索引
            int nextIndex = indexByValue.get(arr1[i]);

            // 5. 判断是否属于同一分组
            if (nextIndex == prevIndex + 1) {
                // 如果连续，更新 prevIndex，继续当前分组
                prevIndex++;
            } else {
                // 如果不连续，增加分组计数，并更新 prevIndex 开始新分组
                prevIndex = nextIndex;
                count++;
            }
        }

        // 6. 返回最终分组数
        return count;
    }

    /**
     * 辅助方法：将数组中的元素映射到其索引。
     *
     * @param arr 要映射的数组
     * @return 元素值到索引的映射
     */
    public static Map<Integer, Integer> mapIndices(int[] arr) {
        return IntStream.range(0, arr.length)
            .boxed()
            .collect(Collectors.toMap(
                i -> arr[i], // 键：数组元素值
                Function.identity() // 值：元素索引
            ));
    }

    public static void main(String[] args) {
        // 示例测试
        int[] arr1 = {1, 4, 3, 2};
        int[] arr2 = {1, 2, 4, 3};
        System.out.println("源数组: " + java.util.Arrays.toString(arr1));
        System.out.println("目标数组: " + java.util.Arrays.toString(arr2));
        System.out.println("所需的最少分组数: " + process(arr1, arr2)); // 预期输出: 3

        int[] arr3 = {1, 2, 3, 4};
        int[] arr4 = {1, 2, 3, 4};
        System.out.println("\n源数组: " + java.util.Arrays.toString(arr3));
        System.out.println("目标数组: " + java.util.Arrays.toString(arr4));
        System.out.println("所需的最少分组数: " + process(arr3, arr4)); // 预期输出: 1

        int[] arr5 = {4, 3, 2, 1};
        int[] arr6 = {1, 2, 3, 4};
        System.out.println("\n源数组: " + java.util.Arrays.toString(arr5));
        System.out.println("目标数组: " + java.util.Arrays.toString(arr6));
        System.out.println("所需的最少分组数: " + process(arr5, arr6)); // 预期输出: 4
    }
}

登录后复制

输出示例：

源数组: [1, 4, 3, 2]
目标数组: [1, 2, 4, 3]
所需的最少分组数: 3

源数组: [1, 2, 3, 4]
目标数组: [1, 2, 3, 4]
所需的最少分组数: 1

源数组: [4, 3, 2, 1]
目标数组: [1, 2, 3, 4]
所需的最少分组数: 4

登录后复制

注意事项与性能分析

数据约束： 该算法依赖于数组中元素值的唯一性。如果存在重复值，则元素到索引的映射将不再唯一，算法需要进行修改以处理这种情况。
时间复杂度：
- 构建索引映射：O(N)，其中 N 是数组的长度。
- 遍历源数组：O(N)，每次查找映射为 O(1)。
- 因此，总时间复杂度为 O(N)。
空间复杂度：
- 存储索引映射：O(N)，因为映射需要存储 N 个键值对。
- 因此，总空间复杂度为 O(N)。