在C ++中将所有1组合在一起所需的最小掉期
问题陈述
给定一个0和1的数组。任务是找到将数组中所有1分组在一起所需的最小交换次数。
示例
如果输入数组={1、0、1、1、0、1}，则需要进行1次交换。即将前0与后1交换。
算法
计算数组中1的总数
如果count是x，那么我们需要找到该数组的长度为x的子数组，其最大数目为1
所需的最小交换数将是长度为x的子数组中的0数，最大为1数
示例
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
int oneCnt = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] == 1) {
++oneCnt;
}
}
int x = oneCnt;
int maxOnes = INT_MIN;
int preCompute[n] = {0};
if (arr[0] == 1) {
preCompute[0] = 1;
}
for (int i = 1; i < n; ++i) {
if (arr[i] == 1) {
preCompute[i] = preCompute[i - 1] + 1;
} else {
preCompute[i] = preCompute[i - 1];
}
}
for (int i = x - 1; i < n; ++i) {
if (i == (x - 1)) {
oneCnt = preCompute[i];
} else {
oneCnt = preCompute[i] - preCompute[i - x];
} if (maxOnes < oneCnt) {
maxOnes = oneCnt;
}
}
int swapCnt = x - oneCnt;
return swapCnt;
}
int main() {
int arr[] = {1, 0, 1, 1, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum swap count = " << getMinSwaps(arr, n) << endl;
return 0;
}当您编译并执行上述程序时。它产生以下输出-
输出结果
Minimum swap count = 1