思路,贪心,首先统计所有1的个数num1,按num1大小的滑动窗口滑过整个数组,窗口内1的个数为m,则需要将窗口外的num1-m个1换进来,交换次数为num1-m,整个滑过后最小值就是答案。
本题可以考虑首尾相连,那就可以构造两个nums相连,横跨的部分就是首尾相连的情况
class Solution {
public:
int minSwaps(vector<int>& nums) {
int num1 = 0;
int n = nums.size();
vector<int> data(2*n);
for(int i = 0; i < 2*n; i++)
data[i] = nums[i%n];
for(auto x : nums) if(x == 1) num1++;
int cnt = 0;
for(int i = 0; i < num1; i++) if(data[i] == 1) cnt++;
int maxm = cnt;
for(int i = 1; i <= data.size() - num1; i++) {
if(data[i-1] == 1) cnt--;
if(data[i+num1-1] == 1) cnt++;
maxm = max(maxm, cnt);
}
return num1 - maxm;
}
};