最小切换以对二进制数组进行分区，以便在C ++中它具有前0到1

问题陈述

给定n个仅包含0和1的整数数组，请找到所需的最小切换（从0切换到1，反之亦然），以使该数组成为分区的数组，即其前0到1。

示例

如果arr [] = {1，0，0，1，1，1，0}，则需要2个切换，即切换第一个和最后一个零。

算法

• 如果我们观察到这个问题，那么我们将发现肯定存在一个从0到n-1的点，其中到该点的所有元素都应包含所有0，而指向该点的右边应包含所有1。

• 那些不遵守该法律的索引将被删除。这个想法是从左到右计算全0。

示例

#include <bits/stdc++.h>
using namespace std;
int getMinToggles(int *arr, int n) {
   int zeroCnt[n + 1] = {0};
   for (int i = 1; i <= n; ++i) {
      if (arr[i - 1] == 0) {
         zeroCnt[i] = zeroCnt[i - 1] + 1;
      } else {
         zeroCnt[i] = zeroCnt[i - 1];
      }
   }
   int result = n;
   for (int i = 1; i <= n; ++i) {
      result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]);
   }
   return result;
}
int main() {
   int arr[] = {1, 0, 0, 1, 1, 1, 0};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Minimum toggles = " << getMinToggles(arr, n) << endl;
   return 0;
}

当您编译并执行上述程序时。它产生以下输出-

输出结果

Minimum toggles = 2