Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

이진 배열에서 1의 가장 긴 연속 시퀀스를 얻기 위해 1로 바꿀 0의 인덱스 찾기 - C++의 Set-2

<시간/>

컨셉

0과 1의 주어진 배열과 관련하여 1의 최대 연속 시퀀스를 얻기 위해 1로 대체될 0의 위치를 ​​결정합니다. 이 경우 예상 시간 복잡도는 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

방법

0의 양쪽에 1의 개수 사용 -

이제 개념은 각 0의 양쪽에 있는 1의 수를 계산하는 것입니다. 여기에서 requiredindex는 주변에 1의 개수가 최대인 0의 인덱스로 취급됩니다. 이 목적과 관련하여 다음 변수가 구현됩니다 -

  • leftCnt - 현재 요소 제로 과소 고려 사항의 왼쪽에 1의 개수를 저장하는 데 사용됩니다.
  • rightCnt - 현재 요소 제로 과소 고려 사항의 오른쪽에 1의 개수를 저장하는 데 사용됩니다.
  • maxIndex - 주변에 최대 1이 있는 0의 인덱스로 처리됩니다.
  • lastInd - 본 마지막 0 요소의 인덱스로 처리됩니다.
  • maxCnt - 인덱스 maxInd의 0이 1로 바뀌면 1의 개수로 처리됩니다.

이제 절차 세부 정보가 아래에 제공됩니다 -

  • 하나가 입력 배열에 나타날 때까지 증가하는 rightCnt를 유지합니다. 인덱스 i에 다음 0이 있다고 가정합니다.

  • 이 0 요소가 첫 번째 0 요소인지 여부를 확인하십시오. 이제 lastInd에 유효한 인덱스 값이 없으면 첫 번째 0요소로 처리됩니다.

  • 따라서 이 경우 lastInd 업데이트는 i로 완료됩니다. 현재 rightCnt의 값은 이 0의 왼쪽에 있는 0의 수입니다.

  • 이 결과로 leftCnt는 rightCnt와 같고 다시 rightCnt의 값을 결정한다. 현재 0 요소가 첫 번째 0이 아닌 경우 index lastInd에 있는 0 주변의 1의 수는 leftCnt + rightCnt에 의해 제공되는 것으로 나타났습니다.

  • 이제 maxCnt는 이 값이 현재 maxCnt가 보유한 값보다 작은 경우 leftCnt + rightCnt + 1 및 maxIndex =lastInd 값을 허용합니다.

  • 현재 rightCnt는 인덱스 i에서 0에 대한 leftCnt가 될 것이고 lastInd는 i와 같을 것입니다. 이제 다시 rightCnt의 값을 결정하고 maxCnt와 1의 수를 비교하고 그에 따라 maxCnt와 maxIndex를 업데이트합니다.

  • 배열의 후속 0 요소에 대해 이 절차를 반복해야 합니다.

  • lastInd는 현재 leftCnt 및 rightCnt가 계산되는 0의 인덱스를 저장하는 것으로 관찰되었습니다.

  • 마지막으로, 1로 대체되기 위해 필요한 인덱스 0은 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