2026-10-17：划分数组的最少相邻交换次数。用go语言，给定一个整数序列 nums，以及两个整数 a、b，且 a 小于 b。我们希望把 nums 调整成

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. 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。
分类结果：

从左到右扫描：

所以最少相邻交换次数是 5。取模后仍然是 5。

• • 遇到 9：第三类，第三类计数变为 1，交换次数不变。

• • 遇到 7：第二类，前面有 1 个第三类，交换次数加 1，累计为 1；第二类计数变为 1。

• • 遇到 5：第二类，前面有 1 个第三类，交换次数加 1，累计为 2；第二类计数变为 2。

• • 遇到 3：第一类，前面有 2 个第二类和 1 个第三类，交换次数加 3，累计为 5。

• • 9 大于 8，属于第三类；

• • 7 在 [4, 8] 内，属于第二类；

• • 5 在 [4, 8] 内，属于第二类；

• • 3 小于 4，属于第一类。

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

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

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

Go完整代码如下：

package main

 import (
    "fmt"
)

 func minAdjacentSwaps(nums []int, a, b int) (ans int) {
    const mod = 1_000_000_007
    cnt1, cnt2 := 0, 0
    for _, x := range nums {
        if x < a { // x 视作 0
            ans += cnt1 + cnt2
        } elseif x <= b { // x 视作 1
            ans += cnt2
            cnt1++
        } else { // x 视作 2
            cnt2++
        }
    }
    return ans % mod
}

 func main() {
    nums := []int{9, 7, 5, 3}
    a := 4
    b := 8
    result := minAdjacentSwaps(nums, a, b)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def min_adjacent_swaps(nums, a, b):
    MOD = 1_000_000_007
    cnt1 = 0
    cnt2 = 0
    ans = 0

     for x in nums:
        if x < a:          # 视作 0
            ans += cnt1 + cnt2
        elif x <= b:       # 视作 1
            ans += cnt2
            cnt1 += 1
        else:              # 视作 2
            cnt2 += 1

     return ans % MOD

 if __name__ == "__main__":
    nums = [9, 7, 5, 3]
    a = 4
    b = 8
    result = min_adjacent_swaps(nums, a, b)
    print(result)

C++完整代码如下：

  

  

using namespace std;

 int minAdjacentSwaps(const vector& nums, int a, int b) {
    constint MOD = 1000000007;
    long long ans = 0;
    int cnt1 = 0, cnt2 = 0;

     for (int x : nums) {
        if (x < a) {               // x 视作 0
            ans += cnt1 + cnt2;
        } elseif (x <= b) {       // x 视作 1
            ans += cnt2;
            ++cnt1;
        } else {                   // x 视作 2
            ++cnt2;
        }
    }

     return static_cast(ans % MOD);
}

 int main() {
    vector nums = {9, 7, 5, 3};
    int a = 4;
    int b = 8;

     int result = minAdjacentSwaps(nums, a, b);
    cout << result << endl;

     return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。