企业官网建设流程全解析

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。

大体步骤如下：

1. 先把数组中的每个元素按大小归成三类：

   • 第一类：小于 a 的元素，最终应该排在最前面。
   • 第二类：在闭区间 [a, b] 内的元素，最终应该排在中间。
   • 第三类：大于 b 的元素，最终应该排在最后面。

   因为题目允许三个部分为空，所以不需要三类都出现；只要最终顺序满足“第一类在前、第二类在中、第三类在后”即可。

2. 目标形态就是：

   • 所有第一类元素排在左边；
   • 所有第二类元素排在中间；
   • 所有第三类元素排在右边。
     同一类元素内部谁前谁后无所谓，因为题目只要求三个连续部分的类别正确。

3. 相邻交换的本质与逆序对有关：

   • 一次相邻交换最多只能消除一个“逆序对”。
   • 所谓逆序对，就是按最终类别顺序来看，本来应该排在后面的元素却出现在了前面。
   • 因此，最少相邻交换次数就等于当前数组中所有跨类别的逆序对数量。
   • 同类别元素之间不需要交换，因为它们的相对顺序不影响结果。

4. 代码使用一次从左到右的扫描来统计这些逆序对。扫描时维护两个计数：

   • 第一个计数：已经扫描过的第二类元素个数，也就是落在 [a, b] 内的元素个数。
   • 第二个计数：已经扫描过的第三类元素个数，也就是大于 b 的元素个数。
     同时用一个变量累计需要的交换次数。

5. 对当前扫描到的元素分情况处理：

   • 如果当前元素小于 a，即属于第一类：
     它最终应该排在最前面。但前面已经扫描过的第二类元素和第三类元素，最终都应该排在它后面。因此，前面每一个第二类元素和每一个第三类元素，都会和当前这个第一类元素构成逆序对。所以把“已扫描的第二类个数 + 已扫描的第三类个数”累加到交换次数中。
   • 如果当前元素在 [a, b] 内，即属于第二类：
     它最终应该排在第三类前面。前面已经扫描过的第三类元素，最终都应该排在它后面。因此，前面每一个第三类元素都会和当前这个第二类元素构成逆序对。所以把“已扫描的第三类个数”累加到交换次数中。然后，把第二类元素的计数加一。
   • 如果当前元素大于 b，即属于第三类：
     它最终应该排在最后面。前面已经扫描过的第一类和第二类元素，最终都应该排在它前面，所以它不会和前面的元素形成逆序对。因此交换次数不增加，只需要把第三类元素的计数加一。

6. 这样扫描完整个数组后，累计得到的交换次数就是所有跨类别逆序对的总数，也就是最少相邻交换次数。由于答案可能很大，最后要对 1,000,000,007 取模。

7. 以题目例子说明：
   nums = [9, 7, 5, 3]，a = 4，b = 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。

8. 总的时间复杂度：
   整个算法只从左到右遍历数组一次，每个元素只做常数次判断和累加操作，所以时间复杂度是 O(n)，其中 n 是数组长度。

9. 总的额外空间复杂度：
   算法只使用了几个变量来记录计数和累计交换次数，没有额外创建与数组长度相关的数据结构，所以额外空间复杂度是 O(1)。输入数组本身不计入额外空间。

因此，总的时间复杂度是 O(n)，总的额外空间复杂度是 O(1)。

Go完整代码如下：

packagemainimport("fmt")funcminAdjacentSwaps(nums[]int,a,bint)(ansint){constmod=1_000_000_007cnt1,cnt2:=0,0for_,x:=rangenums{ifx<a{// x 视作 0ans+=cnt1+cnt2}elseifx<=b{// x 视作 1ans+=cnt2 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):MOD=1_000_000_007cnt1=0cnt2=0ans=0forxinnums:ifx<a:# 视作 0ans+=cnt1+cnt2elifx<=b:# 视作 1ans+=cnt2 cnt1+=1else:# 视作 2cnt2+=1returnans%MODif__name__=="__main__":nums=[9,7,5,3]a=4b=8result=min_adjacent_swaps(nums,a,b)print(result)

C++完整代码如下：

#include<iostream>#include<vector>usingnamespacestd;intminAdjacentSwaps(constvector<int>&nums,inta,intb){constintMOD=1000000007;longlongans=0;intcnt1=0,cnt2=0;for(intx:nums){if(x<a){// x 视作 0ans+=cnt1+cnt2;}elseif(x<=b){// x 视作 1ans+=cnt2;++cnt1;}else{// x 视作 2++cnt2;}}returnstatic_cast<int>(ans%MOD);}intmain(){vector<int>nums={9,7,5,3};inta=4;intb=8;intresult=minAdjacentSwaps(nums,a,b);cout<<result<<endl;return0;}