2026-10-17划分数组的最少相邻交换次数。用go语言给定一个整数序列 nums以及两个整数 a、b且 a 小于 b。我们希望把 nums 调整成这样的顺序从头到尾可以划分成三个连续区间区间允许为空。第一个区间里的所有数都小于 a第二个区间里的所有数都落在 a 到 b 之间包含 a 和 b第三个区间里的所有数都大于 b。一次操作只能交换两个相邻元素。求让 nums 变成上述形式所需的最少相邻交换次数。如果次数很大返回它对 1,000,000,007 取模后的结果。1 nums.length 100000。1 nums[i] 1000000000。1 a b 1000000000。输入 nums [9,7,5,3], a 4, b 8。输出 5。解释一种最佳交换序列如下交换 nums[2] 和 nums[3]。数组变为 [9, 7, 3, 5]。交换 nums[1] 和 nums[2]。数组变为 [9, 3, 7, 5]。交换 nums[0] 和 nums[1]。数组变为 [3, 9, 7, 5]。交换 nums[1] 和 nums[2]。数组变为 [3, 7, 9, 5]。交换 nums[2] 和 nums[3]。数组变为 [3, 7, 5, 9]。这个数组是好数组因为它可以分为 [3]、[7, 5] 和 [9]。题目来自力扣3994。大体步骤如下先把数组中的每个元素按大小归成三类第一类小于 a 的元素最终应该排在最前面。第二类在闭区间 [a, b] 内的元素最终应该排在中间。第三类大于 b 的元素最终应该排在最后面。因为题目允许三个部分为空所以不需要三类都出现只要最终顺序满足“第一类在前、第二类在中、第三类在后”即可。目标形态就是所有第一类元素排在左边所有第二类元素排在中间所有第三类元素排在右边。同一类元素内部谁前谁后无所谓因为题目只要求三个连续部分的类别正确。相邻交换的本质与逆序对有关一次相邻交换最多只能消除一个“逆序对”。所谓逆序对就是按最终类别顺序来看本来应该排在后面的元素却出现在了前面。因此最少相邻交换次数就等于当前数组中所有跨类别的逆序对数量。同类别元素之间不需要交换因为它们的相对顺序不影响结果。代码使用一次从左到右的扫描来统计这些逆序对。扫描时维护两个计数第一个计数已经扫描过的第二类元素个数也就是落在 [a, b] 内的元素个数。第二个计数已经扫描过的第三类元素个数也就是大于 b 的元素个数。同时用一个变量累计需要的交换次数。对当前扫描到的元素分情况处理如果当前元素小于 a即属于第一类它最终应该排在最前面。但前面已经扫描过的第二类元素和第三类元素最终都应该排在它后面。因此前面每一个第二类元素和每一个第三类元素都会和当前这个第一类元素构成逆序对。所以把“已扫描的第二类个数 已扫描的第三类个数”累加到交换次数中。如果当前元素在 [a, b] 内即属于第二类它最终应该排在第三类前面。前面已经扫描过的第三类元素最终都应该排在它后面。因此前面每一个第三类元素都会和当前这个第二类元素构成逆序对。所以把“已扫描的第三类个数”累加到交换次数中。然后把第二类元素的计数加一。如果当前元素大于 b即属于第三类它最终应该排在最后面。前面已经扫描过的第一类和第二类元素最终都应该排在它前面所以它不会和前面的元素形成逆序对。因此交换次数不增加只需要把第三类元素的计数加一。这样扫描完整个数组后累计得到的交换次数就是所有跨类别逆序对的总数也就是最少相邻交换次数。由于答案可能很大最后要对 1,000,000,007 取模。以题目例子说明nums [9, 7, 5, 3]a 4b 8。分类结果9 大于 8属于第三类7 在 [4, 8] 内属于第二类5 在 [4, 8] 内属于第二类3 小于 4属于第一类。从左到右扫描遇到 9第三类第三类计数变为 1交换次数不变。遇到 7第二类前面有 1 个第三类交换次数加 1累计为 1第二类计数变为 1。遇到 5第二类前面有 1 个第三类交换次数加 1累计为 2第二类计数变为 2。遇到 3第一类前面有 2 个第二类和 1 个第三类交换次数加 3累计为 5。所以最少相邻交换次数是 5。取模后仍然是 5。总的时间复杂度整个算法只从左到右遍历数组一次每个元素只做常数次判断和累加操作所以时间复杂度是 O(n)其中 n 是数组长度。总的额外空间复杂度算法只使用了几个变量来记录计数和累计交换次数没有额外创建与数组长度相关的数据结构所以额外空间复杂度是 O(1)。输入数组本身不计入额外空间。因此总的时间复杂度是 O(n)总的额外空间复杂度是 O(1)。Go完整代码如下packagemainimport(fmt)funcminAdjacentSwaps(nums[]int,a,bint)(ansint){constmod1_000_000_007cnt1,cnt2:0,0for_,x:rangenums{ifxa{// x 视作 0anscnt1cnt2}elseifxb{// x 视作 1anscnt2 cnt1}else{// x 视作 2cnt2}}returnans%mod}funcmain(){nums:[]int{9,7,5,3}a:4b:8result:minAdjacentSwaps(nums,a,b)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defmin_adjacent_swaps(nums,a,b):MOD1_000_000_007cnt10cnt20ans0forxinnums:ifxa:# 视作 0anscnt1cnt2elifxb:# 视作 1anscnt2 cnt11else:# 视作 2cnt21returnans%MODif__name____main__:nums[9,7,5,3]a4b8resultmin_adjacent_swaps(nums,a,b)print(result)C完整代码如下#includeiostream#includevectorusingnamespacestd;intminAdjacentSwaps(constvectorintnums,inta,intb){constintMOD1000000007;longlongans0;intcnt10,cnt20;for(intx:nums){if(xa){// x 视作 0anscnt1cnt2;}elseif(xb){// x 视作 1anscnt2;cnt1;}else{// x 视作 2cnt2;}}returnstatic_castint(ans%MOD);}intmain(){vectorintnums{9,7,5,3};inta4;intb8;intresultminAdjacentSwaps(nums,a,b);coutresultendl;return0;}