2134. 最少交换次数来组合所有的 1 II#

题目描述#

交换定义为选中两个互不相同的位置互换值。环形数组 指第一个元素和最后一个元素相邻。

给定一个二进制环形数组 nums，返回在任意位置将数组中的所有 1 聚集在一起所需的最少交换次数。

示例 1：

1
输入：nums = [0,1,0,1,1,0,0]
2
输出：1

示例 2：

1
输入：nums = [0,1,1,1,0,0,1,1,0]
2
输出：2

解法思路#

核心观察：设数组中 1 的总数为 k，则最终聚集成的区域长度一定是 k。选定某个长度为 k 的窗口作为最终聚集区，「把窗口外的 1 换进来、把窗口内的 0 换出去」所需交换次数 = 窗口内 0 的个数 = k − 窗口内 1 的个数。

所以问题变成：在环形数组中找一个长度为 k 的窗口，使其中 1 的个数最多，答案 = k − max_ones。

由于数组是环形的，窗口要能跨越边界，可用 取模运算 模拟（等价于把数组复制一份接在后面滑动）。套用定长滑窗 入-更新-出：右端点 i 进窗，够 k 时更新 max_ones，左端点出窗。注意只滑 n+k-1 步避免重复。

逐步举例（nums=[0,1,1,1,0,0,1,1,0]）：

k = sum(nums) = 5，即需要找长度为 5 的环形窗口。
环形枚举各长度 5 窗口内的 1 个数：

窗口（下标）	窗口内 1 数
0..4 → [0,1,1,1,0]	3
1..5 → [1,1,1,0,0]	3
2..6 → [1,1,0,0,1]	3
3..7 → [1,0,0,1,1]	3
4..8 → [0,0,1,1,0]	2
5..(9) → [0,1,1,0,0]	2
6..(10) → [1,1,0,0,1]	3
7..(11) → [1,0,0,1,1]	3
8..(12) → [0,0,1,1,0]	2

最大 max_ones = 3，最少交换 = k − max_ones = 5 − 3 = 2，与预期一致。

复杂度分析#

时间复杂度：O(n)，一次遍历。
空间复杂度：O(1)。

代码实现#

1
class Solution:
2
    def minSwaps(self, nums: list[int]) -> int:
3
        k = sum(nums)
4
        if k <= 1:
5
            return 0
6

7
        n = len(nums)
8
        cur = sum(nums[:k])
9
        max_ones = cur
10
        for i in range(k, n + k - 1):
11
            cur += nums[i % n] - nums[(i - k) % n]
12
            if cur > max_ones:
13
                max_ones = cur
14

15
        return k - max_ones

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6
from solution import Solution
7

8

9
class TestMinSwaps(unittest.TestCase):
10
    def setUp(self):
11
        self.solution = Solution()
12

13
    def test_example1(self):
14
        self.assertEqual(self.solution.minSwaps([0, 1, 0, 1, 1, 0, 0]), 1)
15

16
    def test_example2(self):
17
        self.assertEqual(self.solution.minSwaps([0, 1, 1, 1, 0, 0, 1, 1, 0]), 2)
18

19
    def test_example3(self):
20
        self.assertEqual(self.solution.minSwaps([1, 1, 0, 0, 1]), 0)
21

22
    def test_all_ones(self):
23
        self.assertEqual(self.solution.minSwaps([1, 1, 1, 1]), 0)
24

25
    def test_all_zeros(self):
26
        self.assertEqual(self.solution.minSwaps([0, 0, 0, 0]), 0)
27

28
    def test_single_one(self):
29
        self.assertEqual(self.solution.minSwaps([1, 0, 0, 0]), 0)
30

31
    def test_circular_case(self):
32
        self.assertEqual(self.solution.minSwaps([1, 0, 0, 1, 0]), 1)
33

34

35
if __name__ == "__main__":
36
    unittest.main()