2026-08-29使數(shù)組變?yōu)槟＝惶鏀?shù)組的最少操作次數(shù)Ⅰ。用go語言有一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k。每次操作可以任選數(shù)組中的一個(gè)元素把它加 1 或減 1花費(fèi) 1 次操作。如果存在兩個(gè)不同的整數(shù) x 和 y且 x 和 y 都在 0 到 k-1 之間使得數(shù)組所有偶數(shù)下標(biāo)位置的元素對(duì) k 取模后都等于 x同時(shí)所有奇數(shù)下標(biāo)位置的元素對(duì) k 取模后都等于 y那么就稱這個(gè)數(shù)組是滿足條件的。問最少需要多少次增減操作才能使給定的數(shù)組變成滿足條件的數(shù)組返回這個(gè)最少操作次數(shù)。1 nums.length 100。1 nums[i] 1000000000。2 k 100。輸入 nums [1,4,2,8], k 3。輸出 2。解釋讓我們?yōu)榕紨?shù)下標(biāo)選擇 x 1 為奇數(shù)下標(biāo)選擇 y 2 。執(zhí)行以下操作將 nums[1] 4 增加 1 得到 nums [1, 5, 2, 8] 。將 nums[2] 2 減少 1 得到 nums [1, 5, 1, 8] 。現(xiàn)在對(duì)于偶數(shù)下標(biāo)nums[i] % k 1 對(duì)于奇數(shù)下標(biāo)nums[i] % k 2 。因此所需的總操作次數(shù)為 2 。題目來自力扣3937。解題思路整體概述本題要求將數(shù)組按奇偶下標(biāo)分成兩組分別選定一個(gè)模k的余數(shù)偶數(shù)下標(biāo)選定x奇數(shù)下標(biāo)選定y且x ≠ y使得兩組元素各自通過“加 1 或減 1”操作變成目標(biāo)余數(shù)的總操作數(shù)最小。由于每次操作只改變數(shù)值 1且最終只需滿足模k的余數(shù)等于目標(biāo)值因此對(duì)于每個(gè)原始數(shù)值我們可以自由調(diào)整其整數(shù)倍部分操作次數(shù)只與它在“模k的圓環(huán)”上到目標(biāo)余數(shù)的最短距離有關(guān)。這樣問題就退化成了對(duì)于一組余數(shù)0 到k-1選取一個(gè)目標(biāo)余數(shù)使所有余數(shù)到該目標(biāo)允許跨周期的圓環(huán)距離之和最小。算法主體分為三部分分組、單組最優(yōu)計(jì)算calc、合并兩組結(jié)果。一、分組遍歷整個(gè)nums數(shù)組根據(jù)下標(biāo)奇偶性分別收集每個(gè)元素對(duì)k取模后的余數(shù)。得到兩個(gè)列表even偶數(shù)下標(biāo)和odd奇數(shù)下標(biāo)。如果數(shù)組長(zhǎng)度為 1則無需任何操作直接返回 0因?yàn)榇藭r(shí)奇偶下標(biāo)無法同時(shí)存在但題目默認(rèn)可接受。二、單組最優(yōu)計(jì)算calc函數(shù)輸入是一個(gè)長(zhǎng)度n的余數(shù)列表a每個(gè)值在[0, k-1]輸出三個(gè)信息mn該組所有元素變成某個(gè)余數(shù)的最小總操作數(shù)mn2該組所有元素變成另一個(gè)不同余數(shù)的次小總操作數(shù)即第二小的總操作數(shù)bestX取得最小值時(shí)對(duì)應(yīng)的那個(gè)余數(shù)。2.1 排序與擴(kuò)展先將列表a升序排序。構(gòu)造擴(kuò)展數(shù)組ext包含原排序數(shù)組的每個(gè)元素以及每個(gè)元素加上k后的值即a[i] k。這樣ext的長(zhǎng)度為2n它相當(dāng)于把余數(shù)放在數(shù)軸上并復(fù)制了一份向右平移一個(gè)周期。2.2 計(jì)算前綴和對(duì)ext求前綴和方便后續(xù)快速求區(qū)間和。2.3 定義計(jì)算函數(shù)calcOp(target)該函數(shù)計(jì)算將原數(shù)組a即排序后的前n個(gè)元素全部變成target模k意義下所需的最小總操作數(shù)。具體做法在排序后的原數(shù)組前n個(gè)元素中二分查找第一個(gè) target的位置記為i。在擴(kuò)展數(shù)組的區(qū)間[i, in)內(nèi)即從i開始連續(xù)取n個(gè)元素二分查找第一個(gè) target k/2 1的位置記為j。這里target k/2 1是分界點(diǎn)因?yàn)閷?duì)于余數(shù)v它離target更近還是離target k更近的分界點(diǎn)大約在target k/2處。將窗口[i, in)分為兩段左段[i, j)這些數(shù)離target更近將它們都減小到target所需操作數(shù)為(區(qū)間和) - (區(qū)間長(zhǎng)度) * target。右段[j, in)這些數(shù)離target k更近將它們都增大到target k所需操作數(shù)為(區(qū)間長(zhǎng)度) * (target k) - (區(qū)間和)。兩段操作數(shù)之和即為calcOp(target)的返回值。注意這里隱含了每個(gè)元素最終變成target或targetk而不會(huì)考慮target-k因?yàn)閷?duì)于原始余數(shù)在[0, k-1]內(nèi)target-k離得更遠(yuǎn)不會(huì)是最優(yōu)選擇。2.4 遍歷候選余數(shù)并維護(hù)最小和次小遍歷排序后的原數(shù)組a[:n]跳過重復(fù)值相同的余數(shù)不會(huì)產(chǎn)生更優(yōu)結(jié)果。對(duì)每個(gè)不同的余數(shù)x調(diào)用calcOp(x)得到操作數(shù)op。用op更新全局最小mn和次小mn2同時(shí)記錄取得最小值的余數(shù)bestX。遍歷結(jié)束后再額外考慮bestX的兩個(gè)相鄰余數(shù)(bestX-1k)%k和(bestX1)%k因?yàn)樽顑?yōu)目標(biāo)可能不在原始數(shù)據(jù)點(diǎn)上而可能出現(xiàn)在其相鄰位置。對(duì)這兩個(gè)候選值調(diào)用calcOp僅用于更新次小值mn2確保最小值的候選余數(shù)仍然為bestX。2.5 返回結(jié)果返回(mn, mn2, bestX)。三、合并兩組結(jié)果分別對(duì)even和odd調(diào)用calc得到偶數(shù)組的(min1x, min2x, bestX)奇數(shù)組的(min1y, min2y, bestY)若bestX ! bestY說明可以分別取這兩個(gè)不同的余數(shù)總操作數(shù)為min1x min1y直接返回。若bestX bestY則必須讓其中一個(gè)組放棄最優(yōu)解改用次優(yōu)解以保證兩個(gè)目標(biāo)余數(shù)不同。此時(shí)總操作數(shù)有兩種可能偶數(shù)用最優(yōu)奇數(shù)用次優(yōu)min1x min2y偶數(shù)用次優(yōu)奇數(shù)用最優(yōu)min2x min1y取兩者較小值返回。四、時(shí)間與空間復(fù)雜度時(shí)間復(fù)雜度單次calc內(nèi)排序?yàn)镺(n log n)遍歷不同余數(shù)最多n次每次calcOp內(nèi)部執(zhí)行兩次二分查找每次O(log n)故單組計(jì)算為O(n log n)。主函數(shù)對(duì)偶、奇兩組各調(diào)用一次整體復(fù)雜度為O(N log N)其中N是數(shù)組長(zhǎng)度N ≤ 100常數(shù)極小。額外空間復(fù)雜度calc中需要存儲(chǔ)擴(kuò)展數(shù)組ext長(zhǎng)度2n和前綴和數(shù)組長(zhǎng)度2n1以及排序后的原數(shù)組均為O(n)。主函數(shù)中存儲(chǔ)偶、奇兩組也各為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 的最小操作次數(shù)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) 中的數(shù)都減小到 target(n-ji)*(targetk)-(sum[in]-sum[j])// [j, in) 中的數(shù)都增大到 targetk}mn,mn2,bestX:math.MaxInt,math.MaxInt,0fori,x:rangea[:n]{ifi0a[i]a[i-1]{// 優(yōu)化相同的值無需重復(fù)計(jì)算continue}op:calcOp(x)// 維護(hù)最小次小操作次數(shù)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 是已經(jīng)取模后的余數(shù)列表非空nlen(a)a_sortedsorted(a)# 擴(kuò)展數(shù)組用于處理跨周期exta_sorted[xkforxina_sorted]prefix[0]*(len(ext)1)fori,vinenumerate(ext):prefix[i1]prefix[i]vdefcalc_op(target):# 將數(shù)組 a 中所有數(shù)變成 target模 k所需的最小操作數(shù)ibisect.bisect_left(a_sorted,target)# 在 ext[i : in] 中找第一個(gè) 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# 遍歷所有不同的余數(shù)值作為候選 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)# 測(cè)試示例if__name____main__:nums[1,4,2,8]k3print(minOperations(nums,k))C完整代碼如下#includeiostream#includevector#includealgorithm#includeclimits#includetupleusingnamespacestd;// 返回最小操作數(shù)次小操作數(shù)最佳余數(shù)tuplelonglong,longlong,intcalc(vectorinta,intk){intna.size();sort(a.begin(),a.end());// 擴(kuò)展每個(gè)數(shù)加 k 放到末尾便于處理周期for(inti0;in;i){a.push_back(a[i]k);}// 前綴和長(zhǎng)整型vectorlonglongsum(2*n1,0);for(inti0;i2*n;i){sum[i1]sum[i]a[i];}// 計(jì)算將所有數(shù)變?yōu)槟?k 等于 target 的最小操作數(shù)autocalcOp[](inttarget)-longlong{// 原數(shù)組前 n 個(gè)中第一個(gè) target 的位置intilower_bound(a.begin(),a.begin()n,target)-a.begin();// 在擴(kuò)展數(shù)組的 [i, in) 區(qū)間中找第一個(gè) 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;// 遍歷所有不同的余數(shù)值作為候選for(inti0;in;i){if(i0a[i]a[i-1])continue;// 跳過重復(fù)值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;}