2024-08-07 最少交换次数来组合所有的 1 II

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

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

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

给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 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 。

解题思路

简单说下思路，目的是将所有的1放在一起，交换不限制位置，所有1的数量是固定的，我们将原始数组分成多种情况，每一组的长度是固定，即所有1的个数，每一组的1的数量之和和所有1的个数差就是需要交换的次数。

如果我们一组一组的去算，那么需要的时间复杂度是 $O(n^2)$，这样可以，但是不是最佳方案，固定长度，一个一个往后移动，这个和滑动窗口的思想简直是一模一样，所以我们可以使用滑动窗口来解决这个问题。

滑动窗口

sliding window protocol，经过演进，滑动窗口现在是一个非常常见的算法，用于解决数组子序列相关问题。

亮点

• 滑动窗口
• 时间复杂度为 O(n)
• 空间复杂度为 O(1)

实现

Method Ⅰ -- time limit exceeded

class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int max = 0;
        for (int i : nums) {
            max += i;
        }
        if (0 == max || max == n) {
            // 边界情况
            return 0;
        }

        int min = 0;
        // 根绝max确定窗口大小
        int left = 0;
        int right = max - 1;
        while (left < n) {
            int count = 0;
            // 计算窗口中有多少个1，max - count 就是需要交换的次数
            for (int i = left; i <= right; i++) {
                // 取模运算，模拟循环数组
                count += nums[i % n];
            }
            min = Math.max(min, count);
            // 滑向下一个窗口的位置
            left++;
            right++;
        }
        return max - min;
    }
}

Method Ⅱ -- the best way

class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int totalOnes = 0;
        for (int i : nums) {
            totalOnes += i;
        }
        if (0 == totalOnes || totalOnes == n) {
            // 边界情况
            return 0;
        }

        int left = 0;
        // 确定边界数值，可以不声明right，来节省一部分空间开销
        int right = left + totalOnes - 1;
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        left++;
        right++;
        int maxOnesInWindow = sum;
        while (left < n) {
            // 计算窗口中有多少个1，max - count 就是需要交换的次数
            // 循环计算的话会超时，所以我们需要换一种思路来解决问题
            // 由于窗口的特性是：减去前一个，加上后一个，这样我们只需要知道第一个窗口有多少个1就可以了
            sum = sum - nums[left - 1] + nums[right % n];
            maxOnesInWindow = Math.max(sum, maxOnesInWindow);
            // 滑向下一个窗口的位置
            left++;
            right++;
        }

        return totalOnes - maxOnesInWindow;
    }
}