C ++で最初に0、次に1になるように、バイナリ配列を分割するための最小トグル

問題の説明

0と1のみを含むn個の整数の配列が与えられた場合、配列がパーティション化される、つまり最初に0、次に1になるように、必要な最小のトグル（0から1に、またはその逆に切り替える）を見つけます。

例

arr [] ={1、0、0、1、1、1、0}の場合、2つのトグルが必要です。つまり、最初の1つと最後のゼロをトグルします。

アルゴリズム

• 質問を観察すると、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