[LeetCode] 1151. Minimum Swaps to Group All 1's 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 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].

Example 4:

Input: 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]
Output: 8

Constraints:

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

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

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

这道题问的是 swap 的次数，但是其实是需要换一个思路思考的，因为这个题你没法总结出来什么样的 swap 策略是最优的。我这里提供一个滑动窗口的思路。这道题前缀和也能做，日后有时间我再补充。同时这道题并不是典型的滑动窗口，需要有一点点变化。

首先统计一下 input 数组里面一共有多少个 1，记为 count，这样我们也就知道了当 swap 完成之后，由 1 组成的子数组的长度是多少。接着我们开始滑动窗口的操作，end 指针一边移动，一边记录 0 的出现次数。当 start 和 end 指针之间的距离 == count 的时候，说明这一段的长度满足，同时又由于我们用 end 指针记录了这一路上 0 的出现次数，所以如果要把目前这一段（end - start + 1）都变成 1，需要 swap 的次数其实就等于这一段里 0 的个数。一直遍历，直到找到最小的 swap 次数。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int minSwaps(int[] data) {
 3         int count = 0;
 4         for (int d : data) {
 5             if (d == 1) {
 6                 count++;
 7             }
 8         }
 9 
10         int len = data.length;
11         int min = Integer.MAX_VALUE;
12         int start = 0;
13         int end = 0;
14         int zeros = 0;
15         while (end < len) {
16             if (data[end] == 0) {
17                 zeros++;
18             }
19             
20             if (end - start + 1 > count) {
21                 if (data[start] == 0) {
22                     zeros--;
23                 }
24                 start++;
25             }
26             if (end - start + 1 == count) {
27                 min = Math.min(min, zeros);
28             }
29             end++;
30         }
31         return min;
32     }
33 }

LeetCode 题目总结