将给定数组转换为目标数组所需的最少分组数求解

核心逻辑 #

问题的本质是：在目标数组中找到最少数量的连续子序列，每个子序列都恰好是输入数组中的某段连续元素（顺序完全一致），且这些子序列能完整覆盖目标数组。通过调整这些子序列的顺序，就能拼接出目标数组。

具体实现步骤 #

1. 建立元素位置映射：
   创建一个哈希表，记录输入数组中每个元素对应的索引位置，这样可以快速查找任意元素在输入数组中的位置，避免重复遍历。

2. 动态规划求解最少片段数：

   • 定义dp数组：dp[i]表示目标数组前i个元素所需的最少片段数。初始化dp[0] = 0（前0个元素不需要片段），其余dp[i]设为一个大于数组长度的数（表示初始不可达）。
   • 遍历目标数组的每个位置i（对应前i个元素），再遍历所有可能的起始位置j（0 ≤ j < i）：
     • 取目标数组子序列T[j..i-1]的第一个元素，通过哈希表找到它在输入数组中的起始位置startPos。
     • 检查该子序列的长度是否超出输入数组的范围，如果超出则跳过。
     • 验证目标数组的这个子序列是否与输入数组中startPos开始的等长连续子序列完全匹配（顺序一致）。
     • 如果匹配，则更新dp[i]为当前dp[i]和dp[j]+1中的较小值。

3. 返回结果：dp[n]（n为数组长度）就是最少需要的片段数。

代码示例（Java） #

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int process(int[] inp, int[] desired) {
        int n = inp.length;
        Map<Integer, Integer> elemPos = new HashMap<>();
        // 记录输入数组中每个元素的索引
        for (int i = 0; i < n; i++) {
            elemPos.put(inp[i], i);
        }
        
        int[] dp = new int[n + 1];
        // 初始化dp数组，默认设为比最大可能值大的数
        for (int i = 1; i <= n; i++) {
            dp[i] = n + 1;
        }
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                int subLen = i - j;
                int firstElem = desired[j];
                int startInInp = elemPos.get(firstElem);
                
                // 输入数组中没有足够长度的连续子序列，跳过
                if (startInInp + subLen > n) {
                    continue;
                }
                
                // 验证目标子序列是否和输入数组的连续子序列匹配
                boolean isMatch = true;
                for (int k = 0; k < subLen; k++) {
                    if (desired[j + k] != inp[startInInp + k]) {
                        isMatch = false;
                        break;
                    }
                }
                
                if (isMatch) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }
}

说明 #

对于长度为1000的数组，上述代码的时间复杂度为O(n²)，完全可以满足性能要求。如果想要进一步优化子序列匹配的效率，可以使用KMP算法预处理输入数组的模式串，但对于本题的约束来说，基础实现已经足够。

内容的提问来源于stack exchange，提问作者Learner