2026-05-21变成目标数组的最少操作次数。用go语言给你两个长度为 n 的整数数组 nums 和 target。nums[i] 表示当前位置 i 的当前值target[i] 表示你希望当前位置 i 最终变成的期望值。你可以进行任意多次操作可以不做。每次操作你要先选定一个整数 x然后在数组 nums 里找出所有“极大连续区间”这些区间里的每个位置都等于 x且该区间在保持全为 x 的前提下不能再向左或向右扩展也就是已经是该值 x 的最长连续段并且是无法再延伸的那种。对每个这样的区间 [l, r]本次操作会把这个区间内的 nums 全部替换成 target 对应位置的值把 nums[l…r] 直接改成 target[l…r]。你的目标是让最终 nums 完全等于 target问最少需要多少次操作。1 n nums.length target.length 100000。1 nums[i], target[i] 100000。输入 nums [1,2,3], target [2,1,3]。输出 2解释选择 x 1极大段 [0, 0] 被更新 - nums 变为 [2, 2, 3]。选择 x 2极大段 [0, 1] 被更新nums[0] 保持为 2nums[1] 变为 1 - nums 变为 [2, 1, 3]。因此将 nums 转换为 target 需要 2 次操作。题目来自力扣3810。一、分步骤详细推演过程初始状态nums[1, 2, 3]target[2, 1, 3]已操作次数0第一步执行第 1 次操作选择 x 1最优选择能最快修正错误位置找 nums 中 x1 的极大连续区间遍历数组只有索引 0 位置是 1左边无元素、右边是 2不是1所以极大区间是[0, 0]。执行替换把 nums[0] 替换成 target[0]值为2。操作后状态nums[2, 2, 3]target[2, 1, 3]已操作次数1第二步执行第 2 次操作选择 x 2当前唯一需要修正的错误值找 nums 中 x2 的极大连续区间遍历数组索引 0、1 都是 2左边无元素、右边是 3不是2所以极大区间是[0, 1]。执行替换把 nums[0~1] 替换成 target[0~1]nums[0] 原本就是2和target一致不变nums[1] 替换成 target[1]值为1。操作后状态nums[2, 1, 3]target[2, 1, 3]已操作次数2第三步终止此时nums与target完全相等停止操作。最终最少操作次数2三、核心解题思路第一步筛选差异位置遍历两个数组找出所有nums[i] ≠ target[i]的位置这些位置是必须通过操作修正的。第二步统计「需要操作的不同数值」每次操作我们只能选择一个数值x批量修正所有x的极大区间。最少操作次数 所有需要修正的位置中不同数值的数量。示例中需要修正的数值是1和2共2个所以答案是2第三步输出结果直接返回统计到的不同数值的个数就是最少操作次数。四、时间复杂度 额外空间复杂度 分析1. 总时间复杂度核心操作一次完整遍历数组遍历所有元素对比nums和target 哈希表插入/查询操作。数组长度为n哈希表的单次操作是O(1)常数时间。总时间复杂度O(n)线性时间处理10万级数据完全高效2. 总额外空间复杂度额外使用了哈希集合存储需要修正的不同数值。哈希集合的最大元素个数最多等于数组长度n极端情况所有位置都需要修正且数值全不同。总额外空间复杂度O(n)线性空间符合题目数据范围要求总结过程先选数值x→找x的最长连续段→批量替换为目标值重复至数组一致最少操作次数 需要修正的不同数值的个数时间复杂度O(n)线性遍历空间复杂度O(n)哈希集合存储差异数值。Go完整代码如下packagemainimport(fmt)funcminOperations(nums,target[]int)int{set:map[int]struct{}{}fori,x:rangenums{ifx!target[i]{set[x]struct{}{}}}returnlen(set)}funcmain(){nums:[]int{1,2,3}target:[]int{2,1,3}result:minOperations(nums,target)fmt.Println(result)}Python完整代码如下package mainimport(fmt)func minOperations(nums,target[]int)int{set:map[int]struct{}{}fori,x:rangenums{ifx!target[i]{set[x]struct{}{}}}returnlen(set)}func main(){nums:[]int{1,2,3}target:[]int{2,1,3}result:minOperations(nums,target)fmt.Println(result)}C完整代码如下#includeiostream#includevector#includeunordered_setusingnamespacestd;intminOperations(vectorintnums,vectorinttarget){unordered_setintset;for(inti0;inums.size();i){if(nums[i]!target[i]){set.insert(nums[i]);}}returnset.size();}intmain(){vectorintnums{1,2,3};vectorinttarget{2,1,3};intresultminOperations(nums,target);coutresultendl;return0;}
