バイナリ配列で1の最長の連続シーケンスを取得するために1に置き換えられる0のインデックスを検索します-C++のSet-2

コンセプト

与えられた0と1の配列に関して、1に置き換えられる0の位置を決定して、1の最大連続シーケンスを取得します。この場合、予想される時間計算量はO（n）であり、補助空間はO（1）です。

入力

arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}

出力

Index 10

配列インデックスを0から開始し、0を1に置き換えます

インデックス10は、1の最長の連続シーケンスを引き起こします。

入力

arr[] = {1, 1, 1, 1, 1, 0}

出力

Index 5

メソッド

ゼロの両側で1のカウントを使用する-

ここでの概念は、各ゼロの両側にある1の数を数えることです。ここで、requiredindexは、周囲に最大数の1を持つゼロのインデックスとして扱われます。この目的に関して、次の変数が実装されています-

• leftCnt-現在の要素0の左側にある1の数を、考慮されていない状態で格納するために使用されます。
• rightCnt-現在の要素0の右側の1の数を、考慮されていない状態で格納するために使用されます。
• maxIndex-ゼロのインデックスとして扱われ、その周りに最大数の1があります。
• lastInd-最後に表示されたゼロ要素のインデックスとして扱われます
• maxCnt-インデックスmaxIndのゼロが1に置き換えられた場合、1のカウントとして扱われます。

手順の詳細を以下に示します-

• 入力配列に1つが存在するまで、rightCntの増分を維持します。次のゼロがインデックスiに存在すると仮定します。

• このゼロ要素が最初のゼロ要素であるかどうかを確認します。 lastIndが有効なインデックス値を保持していない場合、最初のゼロ要素として扱われるようになりました。

• したがって、その場合、lastIndの更新はiで行われます。現在、rightCntの値は、このゼロの左側にあるゼロの数です。

• この結果、leftCntはrightCntに等しくなり、rightCntの値を再度決定します。現在のゼロ要素が最初のゼロでない場合、インデックスlastIndに存在するゼロ付近の1の数は、leftCnt+rightCntによって提供されることがわかっています。

• これで、maxCntは、この値がmaxCntによって現在保持されている値よりも小さい場合、値leftCnt + rightCnt+1およびmaxIndex=lastIndを受け入れます。

• 現在、rightCntはインデックスiでゼロのleftCntになり、lastIndはiに等しくなります。ここで、rightCntの値を再度決定し、その数をmaxCntと比較し、それに応じてmaxCntとmaxIndexを更新します。

• 配列の後続のゼロ要素ごとに、この手順を繰り返す必要があります。

• lastIndは、現在のleftCntとrightCntが計算されるゼロのインデックスを格納することが確認されています。

• 最後に、1に置き換えるために必要なゼロのインデックスがmaxIndexに格納されます。

例

// C++ program to find index of zero
// to be replaced by one to get longest
// continuous sequence of ones.
#include <bits/stdc++.h>
using namespace std;
// Used to returns index of 0 to be replaced
// with 1 to get longest continuous
// sequence of 1s. If there is no 0
// in array, then it returns -1.
int maxOnesIndex(bool arr1[], int n1){
   int i = 0;
   // Used to store count of ones on left
   // side of current element zero
   int leftCnt1 = 0;
   // Used to store count of ones on right
   // side of current element zero
   int rightCnt1 = 0;
   // Shows index of zero with maximum number
   // of ones around it.
   int maxIndex1 = -1;
   // Shows index of last zero element seen
   int lastInd1 = -1;
   // Shows count of ones if zero at index
   // maxInd1 is replaced by one.
   int maxCnt1 = 0;
   while (i < n1) {
      // Used to keep incrementing count until
      // current element is 1.
      if (arr1[i]) {
         rightCnt1++;
      }
      else {
         // It has been observed that if current zero element
         // is not first zero element,
         // then count number of ones
         // obtained by replacing zero at
         // index lastInd. Update maxCnt
         // and maxIndex if required.
         if (lastInd1 != -1) {
            if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
               maxCnt1 = leftCnt1 + rightCnt1 + 1;
               maxIndex1 = lastInd1;
            }
         }
         lastInd1 = i;
         leftCnt1 = rightCnt1;
         rightCnt1 = 0;
      }
      i++;
   }
   // Determine number of ones in continuous
   // sequence when last zero element is
   // replaced by one.
   if (lastInd1 != -1) {
      if (leftCnt1 + rightCnt1 + 1 > maxCnt1) {
         maxCnt1 = leftCnt1 + rightCnt1 + 1;
         maxIndex1 = lastInd1;
      }
   }
   return maxIndex1;
}
// Driver function
int main(){
   bool arr1[] = { 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1 };
   // bool arr1[] = {1, 1, 1, 1, 1, 0};
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   cout << "Index of 0 to be replaced is "
   << maxOnesIndex(arr1, n1);
   return 0;
}

出力

Index of 0 to be replaced is 10