05 August 2008
给一个1D的01数组，求最小的交换任何数的操作，可以让所有1在一起（任何地方）
滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int minSwaps(int[] data) {
// first count number of 1s in the array
int numOfOnes = 0;
for (int num : data) {
if (num == 1) {
numOfOnes++;
}
}
// for every fixed window with size numOnes, the swaps need to do is the number of zeros within this window (or window size - number of ones)
int k = numOfOnes;
int maxOnes = 0;
int windowOnes = 0;
for (int left = 0, right = 0; right < data.length; right++) {
windowOnes += data[right];
if (right - left == k - 1) {
maxOnes = Math.max(maxOnes, windowOnes);
windowOnes -= data[left++];
}
}
return k - maxOnes;
}
}