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

• 标签：数组、滑动窗口
• 难度：中等

题目大意 #

给定一个二进制数组 data。

要求：通过交换位置，将数组中任何位置上的 1 组合到一起，并返回所有可能中所需的最少交换次数。

解题思路 #

将数组中任何位置上的 1 组合到一起，并要求最少的交换次数。也就是说交换之后，某个连续子数组中全是 1，数组其他位置全是 0。为此，我们可以维护一个固定长度为 1 的个数的滑动窗口，找到滑动窗口中 0 最少的个数，这样最终交换出去的 0 最少，交换次数也最少。

求最少交换次数，也就是求滑动窗口中最少的 0 的个数。具体做法如下：

1. 统计 1 的个数，并设置为窗口长度 window_size。使用 window_count 维护窗口中 0 的个数。使用 ans 维护窗口中最少的 0 的个数，也可以叫做最少交换次数。
2. 如果 window_size 为 0，则说明不用交换，直接返回 0。
3. 使用两个指针 left、right。left 、right 都指向数组的第一个元素，即：left = 0，right = 0。
4. 如果 data[right] == 0，则更新窗口中 0 的个数，即 window_count += 1。然后向右移动 right。
5. 当窗口元素个数为 window_size 时，即：right - left + 1 >= window_size 时，更新窗口中最少的 0 的个数。
6. 然后如果左侧 data[left] == 0，则更新窗口中 0 的个数，即 window_count -= 1。然后向右移动 left，从而缩小窗口长度，即 left += 1，使得窗口大小始终保持为 window_size。
7. 重复 4 ~ 6 步，直到 right 到达数组末尾。返回答案 ans。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        window_size = 0
        for item in data:
            if item == 1:
                window_size += 1
        if window_size == 0:
            return 0

        left, right = 0, 0
        window_count = 0
        ans = float('inf')
        while right < len(data):
            if data[right] == 0:
                window_count += 1

            if right - left + 1 >= window_size:
                ans = min(ans, window_count)
                if data[left] == 0:
                    window_count -= 1
                left += 1
            right += 1
        return ans if ans != float('inf') else 0