C++ですべての1をグループ化するために必要な最小スワップ

問題の説明

0と1の配列が与えられます。タスクは、アレイに存在するすべての1をグループ化するために必要なスワップの最小数を見つけることです。

例

入力配列={1、0、1、1、0、1}の場合、1つのスワップが必要です。つまり、最初の0を最後の1と交換します。

アルゴリズム

• 配列内の1の総数を数えます
• countがxの場合、最大数が1のこの配列の長さxのサブ配列を見つける必要があります
• 必要な最小スワップは、長さ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