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

难度: Medium

交换定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形数组是一个数组，可以认为 第一个 元素和 最后一个 元素相邻。

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

示例 1：

输入：nums = [0,1,0,1,1,0,0]
输出：1
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[0,0,1,1,1,0,0] 交换 1 次。
[0,1,1,1,0,0,0] 交换 1 次。
[1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 1 。

示例 2：

输入：nums = [0,1,1,1,0,0,1,1,0]
输出：2
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。
[1,1,1,1,1,0,0,0,0] 交换 2 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 2 。

示例 3：

输入：nums = [1,1,0,0,1]
输出：0
解释：得益于数组的环形特性，所有的 1 已经聚集在一起。
因此，需要的最少交换次数为 0 。

提示：

1 <= nums.length <= 10⁵
nums[i] 为 0 或者 1

Submission

运行时间: 85 ms

内存: 21.0 MB

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n, cnt, nums = len(nums), nums.count(1), nums * 2
        ans = cnt_ = sum(nums[:cnt])
        for i in range(n):
            if nums[i] != nums[i + cnt]:
                cnt_ += nums[i + cnt] - nums[i]
                ans = max(ans, cnt_)
        return cnt - ans

Explain

The solution uses a sliding window approach. First, it counts the number of 1s in the array and duplicates the array to handle the circular nature. Then, it creates a window of size equal to the number of 1s and slides it across the array to find the maximum number of 1s that can be gathered in one window. The minimum number of swaps is then calculated by subtracting this maximum from the total count of 1s.

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n, cnt, nums = len(nums), nums.count(1), nums * 2  # Duplicate the array
        ans = cnt_ = sum(nums[:cnt])  # Initialize the window
        for i in range(n):
            if nums[i] != nums[i + cnt]:
                cnt_ += nums[i + cnt] - nums[i]  # Update the count of 1s in the window
                ans = max(ans, cnt_)
        return cnt - ans  # Calculate the minimum swaps

Explore

首先统计数组中`1`的数量是为了确定滑动窗口的大小，这个大小等于1的总数量，因为我们的目标是尽可能地将所有的1集中到一个连续的区域中。数组翻倍是因为这个问题的数组是环形的，翻倍后可以简化环形数组边界条件的处理。通过翻倍，原本环形的结构被线性化，使得可以用常规的滑动窗口方法来处理可能跨越数组起始和结束边界的情况。

在处理环形数组的边界条件时，通过将数组翻倍来模拟环形结构。这样，可以在一个长度为2倍原数组长度的线性数组上应用滑动窗口，而不必担心窗口跨越数组的起始和结束边界。滑动窗口只需在长度为原数组长度的范围内移动，从而能够覆盖所有可能的连续区域，包括那些跨越原数组边界的区域。

这种更新计数的方法是基于滑动窗口的性质。当窗口向右滑动一位时，窗口最左边的元素（nums[i]）会被移出窗口，而紧接在窗口最右边的下一个元素（nums[i + cnt]）将进入窗口。因此，更新1的数量就是简单地加上新进入窗口的元素值（nums[i + cnt]，如果是1就加1，是0就加0），并减去移出窗口的元素值（nums[i]）。这样可以快速计算出新窗口中1的总数量，而无需重新遍历整个窗口。

`ans`在此题解中代表在任意连续的由`cnt`个元素组成的窗口中，能够找到的最大的1的数量。因此，`cnt - ans`就是在最优情况下，即1已经尽可能多地聚集在一起时，窗口中还需要通过交换添加的1的数量，这也就是最少需要进行的交换次数。这是因为如果一个窗口已经包含了尽可能多的1，那么窗口外剩余的1就需要与窗口内的0进行交换，以实现所有1的聚集。