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

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

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

示例 1:

输入: data = [1,0,1,0,1]
输出: 1
解释: 
有三种可能的方法可以把所有的 1 组合在一起：
[1,1,1,0,0]，交换 1 次；
[0,1,1,1,0]，交换 2 次；
[0,0,1,1,1]，交换 1 次。
所以最少的交换次数为 1。

示例  2:

输入：data = [0,0,0,1,0]
输出：0
解释： 
由于数组中只有一个 1，所以不需要交换。

示例 3:

输入：data = [1,0,1,0,1,0,0,1,1,0,1]
输出：3
解释：
交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。

示例 4:

输入: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]
输出: 8

提示:

• 1 <= data.length <= 10^5
• data[i] == 0 or 1.

提示 1

How many 1's should be grouped together ? Is not a fixed number?

提示 2

Yeah it's just the number of 1's the whole array has. Let's name this number as ones

提示 3

Every subarray of size of ones, needs some number of swaps to reach, Can you find the number of swaps needed to group all 1's in this subarray?

提示 4

It's the number of zeros in that subarray.

提示 5

Do you need to count the number of zeros all over again for every position ?

提示 6

Use Sliding Window technique.

解法：定长滑动窗口

class Solution {
    public int minSwaps(int[] data) {
        int n = data.length;
        // ones表示数组中1的数目
        int ones = 0;
        int ans = Integer.MAX_VALUE;
        // swaps表示窗口内0的数目
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            ones += data[i];
        }
        if (ones <= 1) {
            return 0;
        }
        // 定长窗口，起始窗口为data[0,..,ones - 1]
        int left = 0;
        int right = 0;
        for (; right < ones - 1; right++) {
            swaps += data[right] == 0 ? 1 : 0;
        }
        while (right < n) {
            swaps += data[right] == 0 ? 1 : 0;
            ans = Math.min(ans, swaps);
            swaps -= data[left] == 0 ? 1 : 0;
            left++;
            right++;
        }
        return ans;
    }
}

复杂度分析 

• 时间复杂度：O(n)，n 是 数组data 的长度。
• 空间复杂度：O(1)。

另一种写法：

class Solution {
    public int minSwaps(int[] data) {
        int n = data.length;
        // ones表示数组中1的数目
        int ones = 0;
        int ans = Integer.MAX_VALUE;
        // swaps表示窗口内0的数目
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            ones += data[i];
        }
        int left = 0;
        int right = 0;
        while (right < n) {
            swaps += data[right] == 0 ? 1 : 0;
            if (right - left + 1 == ones) {
                ans = Math.min(ans, swaps);
                swaps -= data[left] == 0 ? 1 : 0;
                left++;
            }
            right++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

复杂度分析 

• 时间复杂度：O(n)，n 是 数组data 的长度。
• 空间复杂度：O(1)。