2026-08-29使数组变为模交替数组的最少操作次数Ⅰ。用go语言有一个整数数组 nums 和一个整数 k。每次操作可以任选数组中的一个元素把它加 1 或减 1花费 1 次操作。如果存在两个不同的整数 x 和 y且 x 和 y 都在 0 到 k-1 之间使得数组所有偶数下标位置的元素对 k 取模后都等于 x同时所有奇数下标位置的元素对 k 取模后都等于 y那么就称这个数组是满足条件的。问最少需要多少次增减操作才能使给定的数组变成满足条件的数组返回这个最少操作次数。1 nums.length 100。1 nums[i] 1000000000。2 k 100。输入 nums [1,4,2,8], k 3。输出 2。解释让我们为偶数下标选择 x 1 为奇数下标选择 y 2 。执行以下操作将 nums[1] 4 增加 1 得到 nums [1, 5, 2, 8] 。将 nums[2] 2 减少 1 得到 nums [1, 5, 1, 8] 。现在对于偶数下标nums[i] % k 1 对于奇数下标nums[i] % k 2 。因此所需的总操作次数为 2 。题目来自力扣3937。解题思路整体概述本题要求将数组按奇偶下标分成两组分别选定一个模k的余数偶数下标选定x奇数下标选定y且x ≠ y使得两组元素各自通过“加 1 或减 1”操作变成目标余数的总操作数最小。由于每次操作只改变数值 1且最终只需满足模k的余数等于目标值因此对于每个原始数值我们可以自由调整其整数倍部分操作次数只与它在“模k的圆环”上到目标余数的最短距离有关。这样问题就退化成了对于一组余数0 到k-1选取一个目标余数使所有余数到该目标允许跨周期的圆环距离之和最小。算法主体分为三部分分组、单组最优计算calc、合并两组结果。一、分组遍历整个nums数组根据下标奇偶性分别收集每个元素对k取模后的余数。得到两个列表even偶数下标和odd奇数下标。如果数组长度为 1则无需任何操作直接返回 0因为此时奇偶下标无法同时存在但题目默认可接受。二、单组最优计算calc函数输入是一个长度n的余数列表a每个值在[0, k-1]输出三个信息mn该组所有元素变成某个余数的最小总操作数mn2该组所有元素变成另一个不同余数的次小总操作数即第二小的总操作数bestX取得最小值时对应的那个余数。2.1 排序与扩展先将列表a升序排序。构造扩展数组ext包含原排序数组的每个元素以及每个元素加上k后的值即a[i] k。这样ext的长度为2n它相当于把余数放在数轴上并复制了一份向右平移一个周期。2.2 计算前缀和对ext求前缀和方便后续快速求区间和。2.3 定义计算函数calcOp(target)该函数计算将原数组a即排序后的前n个元素全部变成target模k意义下所需的最小总操作数。具体做法在排序后的原数组前n个元素中二分查找第一个 target的位置记为i。在扩展数组的区间[i, in)内即从i开始连续取n个元素二分查找第一个 target k/2 1的位置记为j。这里target k/2 1是分界点因为对于余数v它离target更近还是离target k更近的分界点大约在target k/2处。将窗口[i, in)分为两段左段[i, j)这些数离target更近将它们都减小到target所需操作数为(区间和) - (区间长度) * target。右段[j, in)这些数离target k更近将它们都增大到target k所需操作数为(区间长度) * (target k) - (区间和)。两段操作数之和即为calcOp(target)的返回值。注意这里隐含了每个元素最终变成target或targetk而不会考虑target-k因为对于原始余数在[0, k-1]内target-k离得更远不会是最优选择。2.4 遍历候选余数并维护最小和次小遍历排序后的原数组a[:n]跳过重复值相同的余数不会产生更优结果。对每个不同的余数x调用calcOp(x)得到操作数op。用op更新全局最小mn和次小mn2同时记录取得最小值的余数bestX。遍历结束后再额外考虑bestX的两个相邻余数(bestX-1k)%k和(bestX1)%k因为最优目标可能不在原始数据点上而可能出现在其相邻位置。对这两个候选值调用calcOp仅用于更新次小值mn2确保最小值的候选余数仍然为bestX。2.5 返回结果返回(mn, mn2, bestX)。三、合并两组结果分别对even和odd调用calc得到偶数组的(min1x, min2x, bestX)奇数组的(min1y, min2y, bestY)若bestX ! bestY说明可以分别取这两个不同的余数总操作数为min1x min1y直接返回。若bestX bestY则必须让其中一个组放弃最优解改用次优解以保证两个目标余数不同。此时总操作数有两种可能偶数用最优奇数用次优min1x min2y偶数用次优奇数用最优min2x min1y取两者较小值返回。四、时间与空间复杂度时间复杂度单次calc内排序为O(n log n)遍历不同余数最多n次每次calcOp内部执行两次二分查找每次O(log n)故单组计算为O(n log n)。主函数对偶、奇两组各调用一次整体复杂度为O(N log N)其中N是数组长度N ≤ 100常数极小。额外空间复杂度calc中需要存储扩展数组ext长度2n和前缀和数组长度2n1以及排序后的原数组均为O(n)。主函数中存储偶、奇两组也各为O(N)。总额外空间为O(N)。Go完整代码如下packagemainimport(fmtmathslicessort)funccalc(a[]int,kint)(int,int,int){n:len(a)slices.Sort(a)for_,x:rangea{aappend(a,xk)}sum:make([]int,n*21)fori,x:rangea{sum[i1]sum[i]x}// 都变成 target 的最小操作次数calcOp:func(targetint)int{i:sort.SearchInts(a[:n],target)j:isort.SearchInts(a[i:in],targetk/21)return(sum[j]-sum[i])-(j-i)*target// [i, j) 中的数都减小到 target(n-ji)*(targetk)-(sum[in]-sum[j])// [j, in) 中的数都增大到 targetk}mn,mn2,bestX:math.MaxInt,math.MaxInt,0fori,x:rangea[:n]{ifi0a[i]a[i-1]{// 优化相同的值无需重复计算continue}op:calcOp(x)// 维护最小次小操作次数ifopmn{mn2mn mn,bestXop,x}elseifopmn2{mn2op}}// 还可以都变成 bestX-1 或者 bestX1mn2min(mn2,calcOp((bestX-1k)%k),calcOp((bestX1)%k))returnmn,mn2,bestX}funcminOperations(nums[]int,kint)int{iflen(nums)1{return0}a:[2][]int{}fori,x:rangenums{a[i%2]append(a[i%2],x%k)}min1x,min2x,bestX:calc(a[0],k)min1y,min2y,bestY:calc(a[1],k)ifbestX!bestY{returnmin1xmin1y}returnmin(min1xmin2y,min2xmin1y)}funcabs(xint)int{ifx0{return-x}returnx}funcmain(){nums:[]int{1,4,2,8}k:3result:minOperations(nums,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importbisectimportmathdefcalc(a,k):# a 是已经取模后的余数列表非空nlen(a)a_sortedsorted(a)# 扩展数组用于处理跨周期exta_sorted[xkforxina_sorted]prefix[0]*(len(ext)1)fori,vinenumerate(ext):prefix[i1]prefix[i]vdefcalc_op(target):# 将数组 a 中所有数变成 target模 k所需的最小操作数ibisect.bisect_left(a_sorted,target)# 在 ext[i : in] 中找第一个 target k//2 1 的位置jbisect.bisect_left(ext,targetk//21,i,in)cnt1j-i sum1prefix[j]-prefix[i]cnt2n-cnt1 sum2prefix[in]-prefix[j]# 前半部分减小到 target后半部分增大到 targetkops(sum1-cnt1*target)(cnt2*(targetk)-sum2)returnops mnmath.inf mn2math.inf best_x0# 遍历所有不同的余数值作为候选 targetprevNoneforxina_sorted:ifxprev:continueprevx opcalc_op(x)ifopmn:mn2mn mnop best_xxelifopmn2:mn2op# 再尝试 best_x 的相邻值模 k 意义下fordeltain(-1,1):cand(best_xdelta)%k opcalc_op(cand)ifopmn:mn2mn mnop best_xcandelifopmn2:mn2opreturnmn,mn2,best_xdefminOperations(nums,k):iflen(nums)1:return0even[nums[i]%kforiinrange(0,len(nums),2)]odd[nums[i]%kforiinrange(1,len(nums),2)]min1x,min2x,best_xcalc(even,k)min1y,min2y,best_ycalc(odd,k)ifbest_x!best_y:returnmin1xmin1yelse:returnmin(min1xmin2y,min2xmin1y)# 测试示例if__name____main__:nums[1,4,2,8]k3print(minOperations(nums,k))C完整代码如下#includeiostream#includevector#includealgorithm#includeclimits#includetupleusingnamespacestd;// 返回最小操作数次小操作数最佳余数tuplelonglong,longlong,intcalc(vectorinta,intk){intna.size();sort(a.begin(),a.end());// 扩展每个数加 k 放到末尾便于处理周期for(inti0;in;i){a.push_back(a[i]k);}// 前缀和长整型vectorlonglongsum(2*n1,0);for(inti0;i2*n;i){sum[i1]sum[i]a[i];}// 计算将所有数变为模 k 等于 target 的最小操作数autocalcOp[](inttarget)-longlong{// 原数组前 n 个中第一个 target 的位置intilower_bound(a.begin(),a.begin()n,target)-a.begin();// 在扩展数组的 [i, in) 区间中找第一个 target k/2 1 的位置intji(lower_bound(a.begin()i,a.begin()in,targetk/21)-(a.begin()i));// 左半部分[i, j)缩小到 target右半部分[j, in)增大到 targetklonglongops(sum[j]-sum[i])-(longlong)(j-i)*target(longlong)(n-ji)*(targetk)-(sum[in]-sum[j]);returnops;};longlongmnLLONG_MAX,mn2LLONG_MAX;intbestX0;// 遍历所有不同的余数值作为候选for(inti0;in;i){if(i0a[i]a[i-1])continue;// 跳过重复值intxa[i];longlongopcalcOp(x);if(opmn){mn2mn;mnop;bestXx;}elseif(opmn2){mn2op;}}// 再尝试 bestX 的相邻值模 k 意义下intcand1(bestX-1k)%k;intcand2(bestX1)%k;mn2min(mn2,calcOp(cand1));mn2min(mn2,calcOp(cand2));return{mn,mn2,bestX};}longlongminOperations(vectorintnums,intk){if(nums.size()1)return0;vectorinteven,odd;for(inti0;i(int)nums.size();i){if(i%20)even.push_back(nums[i]%k);elseodd.push_back(nums[i]%k);}auto[min1x,min2x,bestX]calc(even,k);auto[min1y,min2y,bestY]calc(odd,k);if(bestX!bestY){returnmin1xmin1y;}else{returnmin(min1xmin2y,min2xmin1y);}}intmain(){vectorintnums{1,4,2,8};intk3;coutminOperations(nums,k)endl;return0;}