[LeetCode] 1151. Minimum Swaps to Group All 1s Together

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

Example 1:
Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1’s together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2:
Input: data = [0,0,0,1,0]
Output: 0
Explanation: Since there is only one 1 in the array, no swaps are needed.

Example 3:
Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

Constraints:
1 <= data.length <= 105
data[i] is either 0 or 1.

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

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

思路

这道题问的是 swap 的次数，注意 swap 的策略是有好坏的，这也就是为什么例子一有三种 swap 的结果但是这三种策略的代价是不一样的。思路是固定尺寸的滑动窗口。滑动窗口的尺寸就是 1 的个数。

首先我们用一个变量 ones 记录 input 数组中一共有多少个 1。然后我们用滑动窗口的模板开始扫描 input 数组，当 end 指针遇到 1 的时候，count++；当 end 和 start 两个指针的距离 == ones 的时候，此时我们看一下 end 和 start 之间有几个 1，此时 ones 和 count 的差值就是需要 swap 的次数。遍历整个数组，找到全局最小的 swap 次数即可。

复杂度

时间O(n)
空间O(1)

代码一

Java实现

class Solution {
    public int minSwaps(int[] data) {
        int ones = 0;
        for (int d : data) {
            if (d == 1) {
                ones++;
            }
        }
        // corner case
        if (ones == 0) {
            return 0;
        }

        // normal case
        int start = 0;
        int end = 0;
        int count = 0;
        int res = Integer.MAX_VALUE;
        while (end < data.length) {
            if (data[end] == 1) {
                count++;
            }
            end++;
            if (end - start == ones) {
                res = Math.min(res, ones - count);
                if (data[start] == 1) {
                    count--;
                }
                start++;
            }
        }
        return res;
    }
}

代码二

我再提供一个固定尺寸的滑动窗口的做法。如果全局一共有 k 个 1，那么我们先看前 k 个元素里有几个 1，得到一个 swap 的次数。之后我们遍历完之后所有的数字，看看过程中 swap 的次数是不是最小的，如果是的话，我们更新最小的 swap 次数。

Java实现

class Solution {
    public int minSwaps(int[] data) {
        int n = data.length;
        int k = 0;
        for (int num : data) {
            if (num == 1) {
                k++;
            }
        }

        int count = 0;
        for (int i = 0; i < k; i++) {
            if (data[i] == 1) {
                count++;
            }
        }
        int swap = k - count;

        for (int i = k; i < n; i++) {
            if (data[i] == 1) {
                count++;
            }
            if (data[i - k] == 1) {
                count--;
            }
            swap = Math.min(swap, k - count);
        }
        return swap;
    }
}

相关题目

1151. Minimum Swaps to Group All 1s Together
2134. Minimum Swaps to Group All 1s Together II