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^5
  • nums[i] 是 0 或 1

解题思路

这道题的核心思路是利用滑动窗口技术来解决循环数组中的分组问题。

首先，我们需要明确一个关键观察：要将所有的1聚集在一起，最终形成的连续1的个数是固定的，就是原数组中1的总数。设这个数量为 total。

接下来的问题变成：在所有长度为 total 的子数组中，哪个子数组需要最少的交换次数来变成全1？答案是包含最多1的那个子数组，因为需要交换的次数等于子数组中0的个数。

由于数组是循环的，我们需要考虑跨越数组边界的子数组。一个巧妙的处理方法是将原数组复制一份接在后面，这样就能用普通的滑动窗口来处理所有可能的情况。

具体算法步骤：

  1. 统计数组中1的总数 total，如果为0则直接返回0
  2. 将数组扩展为原来的两倍长度
  3. 使用长度为 total 的滑动窗口，统计每个窗口中1的个数
  4. 返回 total - 最大1个数，即最少需要交换的0的个数

时间复杂度为O(n)，空间复杂度为O(1)（不考虑扩展数组的话）。

代码实现

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        int total = count(nums.begin(), nums.end(), 1);
        
        if (total == 0) return 0;
        
        // 扩展数组以处理循环性质
        vector<int> extended(nums);
        extended.insert(extended.end(), nums.begin(), nums.end());
        
        // 滑动窗口统计最大1的个数
        int maxOnes = 0, currentOnes = 0;
        
        // 初始窗口
        for (int i = 0; i < total; i++) {
            currentOnes += extended[i];
        }
        maxOnes = currentOnes;
        
        // 滑动窗口
        for (int i = total; i < n + total; i++) {
            currentOnes = currentOnes - extended[i - total] + extended[i];
            maxOnes = max(maxOnes, currentOnes);
        }
        
        return total - maxOnes;
    }
};

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        total = sum(nums)
        
        if total == 0:
            return 0
        
        # 扩展数组以处理循环性质
        extended = nums + nums
        
        # 滑动窗口统计最大1的个数
        max_ones = 0
        current_ones = sum(extended[:total])
        max_ones = current_ones
        
        # 滑动窗口
        for i in range(total, n + total):
            current_ones = current_ones - extended[i - total] + extended[i]
            max_ones = max(max_ones, current_ones)
        
        return total - max_ones

public class Solution {
    public int MinSwaps(int[] nums) {
        int n = nums.Length;
        int total = nums.Sum();
        
        if (total == 0) return 0;
        
        // 扩展数组以处理循环性质
        int[] extended = new int[2 * n];
        Array.Copy(nums, 0, extended, 0, n);
        Array.Copy(nums, 0, extended, n, n);
        
        // 滑动窗口统计最大1的个数
        int maxOnes = 0, currentOnes = 0;
        
        // 初始窗口
        for (int i = 0; i < total; i++) {
            currentOnes += extended[i];
        }
        maxOnes = currentOnes;
        
        // 滑动窗口
        for (int i = total; i < n + total; i++) {
            currentOnes = currentOnes - extended[i - total] + extended[i];
            maxOnes = Math.Max(maxOnes, currentOnes);
        }
        
        return total - maxOnes;
    }
}

var minSwaps = function(nums) {
    const totalOnes = nums.reduce((sum, num) => sum + num, 0);
    if (totalOnes <= 1) return 0;
    
    const n = nums.length;
    let maxOnes = 0;
    let currentOnes = 0;
    
    // Initial window
    for (let i = 0; i < totalOnes; i++) {
        currentOnes += nums[i];
    }
    maxOnes = currentOnes;
    
    // Sliding window
    for (let i = 0; i < n; i++) {
        currentOnes = currentOnes - nums[i] + nums[(i + totalOnes) % n];
        maxOnes = Math.max(maxOnes, currentOnes);
    }
    
    return totalOnes - maxOnes;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次：一次统计1的总数，一次滑动窗口
空间复杂度O(n)需要额外空间存储扩展后的数组

相关题目