将数组转换为目标数组所需的最少分组数-java教程-PHP中文网

将数组转换为目标数组所需的最少分组数

聖光之護

发布： 2025-11-22 19:40:02

原创

110人浏览过

将数组转换为目标数组所需的最少分组数

本文探讨了如何将一个给定数组通过最少数量的切割和重新排列，转换为另一个目标数组。核心思想是利用哈希映射记录目标数组中元素的位置，然后遍历原始数组，通过比较元素在目标数组中的相对位置来识别连续的“块”。当相邻元素在目标数组中的位置不连续时，即认为需要一个新的分组，最终统计出的分组数量即为所需的最少切割次数。

在许多数据处理和算法问题中，我们经常需要对数组进行转换。一个常见的问题是：给定两个具有相同唯一元素的数组，我们希望通过最少次数的切割（将原始数组分割成多个连续子数组）和重新排列这些子数组，来形成目标数组。本文将详细介绍解决此类问题的有效算法。

问题描述

假设我们有一个原始数组 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 个片段。

约束条件：

数组中的值是唯一的。
两个数组的长度相同，最大可达 1000。
数组中的值是整数。

初始尝试与误区

一种直观但错误的方法是简单地比较两个数组在相同索引处的元素，并统计不匹配的数量。例如，以下代码片段展示了这种思路：

public int process(int[] inp, int[] desired) {
   int ans = 0;
   for (int i = 0; i < inp.length; i++) {
      if (inp[i] != desired[i]) ans++;
   }
   return ans;
}

登录后复制

这种方法的问题在于，它只计算了元素位置不匹配的数量，而没有考虑到我们可以通过切割和重新排列来移动连续的块。例如，对于 [1,4,3,2] 和 [1,2,4,3]，该方法会返回 3 (因为 4!=2, 3!=4, 2!=3)，但这并不能反映我们真正需要的最少切割数。核心在于，如果 arr1 中的两个相邻元素在 arr2 中也是相邻的，那么它们可以被视为一个整体，不需要切割。

正确的算法思路

解决此问题的关键在于理解“连续片段”的含义。如果 arr1 中的两个相邻元素 arr1[i] 和 arr1[i+1] 在 arr2 中也恰好是相邻的（即 arr1[i] 在 arr2 中的索引是 k，而 arr1[i+1] 在 arr2 中的索引是 k+1），那么这两个元素在转换过程中可以保持在一起，构成一个不需要额外切割的块。反之，如果它们在 arr2 中不相邻，则意味着 arr1[i+1] 必须开始一个新的片段。

数组应用&二维数组 word版

所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。数组是在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。数组应用&二维数组目录 1. 数组的简单应用2. 数组排序3. 数组查找4. 数组的使用思想5. 查表法6. 二维数组7. 数组综合

查看详情

基于此，我们可以采用以下步骤：

构建目标数组索引映射： 由于数组中的元素是唯一的，我们可以创建一个哈希映射（Map<Integer, Integer>），将 arr2 中的每个元素值映射到它在 arr2 中的索引。这使得我们能够快速查询 arr1 中的任意元素在 arr2 中的“目标位置”。
遍历原始数组并计数：
- 初始化一个计数器 count = 1，因为 arr1 中的第一个元素总是会开始第一个片段。
- 获取 arr1 中第一个元素在 arr2 中的索引，并将其存储为 prevIndex。
- 从 arr1 的第二个元素开始遍历。对于每个元素 arr1[i]：
  - 查询 arr1[i] 在 arr2 中的索引，记为 nextIndex。
  - 比较 nextIndex 和 prevIndex。
    - 如果 nextIndex 等于 prevIndex + 1，这意味着 arr1[i-1] 和 arr1[i] 在 arr2 中是连续的。它们属于同一个片段，我们只需更新 prevIndex = nextIndex。
    - 如果 nextIndex 不等于 prevIndex + 1，这意味着 arr1[i] 在 arr2 中的位置与 arr1[i-1] 不连续。因此，arr1[i] 必须开始一个新的片段。此时，我们递增 count，并更新 prevIndex = nextIndex。
- 遍历结束后，count 的值就是将 arr1 转换为 arr2 所需的最少片段数。

算法实现（Java）

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

public class ArrayTransformationGroups {

    /**
     * 计算将 arr1 转换为 arr2 所需的最少分组数。
     *
     * @param arr1 原始数组。
     * @param arr2 目标数组。
     * @return 最少分组数。
     */
    public static int process(int[] arr1, int[] arr2) {
        // 1. 构建目标数组 arr2 的值到索引的映射
        Map<Integer, Integer> indexByValue = mapIndices(arr2);

        // 如果数组为空，则不需要分组
        if (arr1.length == 0) {
            return 0;
        }

        // 2. 初始化分组计数，第一个元素总是开始一个新分组
        int count = 1;

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

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

            // 检查当前元素是否与前一个元素在 arr2 中保持连续顺序
            if (nextIndex == prevIndex + 1) {
                // 如果连续，则属于同一个分组，更新 prevIndex
                prevIndex = nextIndex;
            } else {
                // 如果不连续，则 arr1[i] 开始一个新的分组
                count++;
                prevIndex = nextIndex; // 更新 prevIndex 为当前元素的目标索引
            }
        }

        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("所需的最少分组数: " + process(arr1, arr2)); // 预期输出: 3

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

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

登录后复制

代码解释：

mapIndices(int[] arr) 方法：这是一个辅助方法，用于快速构建从元素值到其在数组中索引的映射。它利用 Java 8 的 IntStream 和 Collectors.toMap 来简洁地实现这一功能。
process(int[] arr1, int[] arr2) 方法：
- 首先调用 mapIndices 为 arr2 创建索引映射。
- count 初始化为 1，因为即使只有一个元素，它也算一个片段。
- prevIndex 存储 arr1 中前一个元素在 arr2 中的目标索引。
- 循环从 arr1 的第二个元素开始。在每次迭代中，它查找当前元素 arr1[i] 在 arr2 中的目标索引 nextIndex。
- 如果 nextIndex 等于 prevIndex + 1，则表示这两个元素在 arr2 中是连续的，它们可以归为一个片段。
- 否则，表示它们不连续，需要一个新的片段，因此 count 递增。
- 无论是否增加 count，prevIndex 都会更新为当前的 nextIndex，为下一个元素的比较做准备。

复杂度分析

时间复杂度：
- 构建索引映射 mapIndices 需要遍历 arr2 一次，时间复杂度为 O(N)，其中 N 是数组的长度。
- process 方法遍历 arr1 一次，并在每次迭代中进行哈希表的查找操作（平均 O(1)）。因此，这一步的时间复杂度为 O(N)。
- 总的时间复杂度为 O(N)。
空间复杂度：
- 哈希映射 indexByValue 需要存储 arr2 中所有元素的索引，因此空间复杂度为 O(N)。