# 1151. Minimum Swaps to Group All 1's Together 最少交换次数来组合所有的 1

@TOC

## # 题目描述

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: [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: [0,0,0,1,0]
Output: 0
Explanation:
Since there is only one 1 in the array, no swaps needed.
``````

Example 3:

``````Input: [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].
``````

Note:

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

## # 解题方法

### # 滑动窗口

1. 首先统计总的有N个1
2. 设置大小为N的滑动窗口，统计该滑动窗口中的1的个数最大值是K
3. 需要交换N - K次使得该滑动窗口内的0变成1

C++代码如下：

``````class Solution {
public:
int minSwaps(vector<int>& data) {
int N = accumulate(data.begin(), data.end(), 0);
int left = -N;
int right = 0;
int one_counts = 0;
int K = 0;
while (right < data.size()) {
if (data[right] == 1) {
one_counts ++;
}
if (left >= 0 && data[left] == 1) {
one_counts --;
}
K = max(K, one_counts);
left ++;
right ++;
}
return N - K;
}
};
``````

## # 日期

2019 年 9 月 23 日 —— 昨夜睡的早，错过了北京的烟火