在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