查找索引0替换为1以获取二进制数组中最长的连续1序列-C ++中的Set-2

概念

对于给定的0s和1s数组,确定要用1替换的0位置以获得最大的1s连续序列。在这种情况下,预期时间复杂度为O(n),辅助空间为O(1)。

输入值

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

输出结果

Index 10

令数组索引从0开始,在0处将0替换为1

索引10导致最长的连续序列1s。

输入值

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

输出结果

Index 5

方法

在零的两边使用一的计数-

现在,概念是计算每个零的两边的个数。在此,所需索引被视为零索引,其周围具有最大的1。为此目的实现了以下变量-

  • leftCnt-用于在考虑中的当前元素零的左侧存储1的计数。

  • rightCnt-用于在考虑中的当前元素零的右侧存储1的计数。

  • maxIndex-它被视为零的索引,最大索引数为零。

  • lastInd-视为所看到的最后零个元素的索引

  • maxCnt-如果将索引maxInd的零替换为1,则视为1的计数。

现在程序细节如下-

  • 保持递增rightCnt直到输入数组中存在一个。假设下一个零出现在索引i处。

  • 验证此零元素是否为第一个零元素。现在,如果lastInd没有任何有效的索引值,它将被视为第一个零元素。

  • 因此,在那种情况下,用i完成lastInd的更新。目前rightCnt的值是该零左侧的零个数。

  • 结果,leftCnt等于rightCnt,然后再次确定rightCnt的值。可以看出,如果当前零元素不是第一个零,则由lastCnt + rightCnt提供存在于索引lastInd的零附近的数字。

  • 现在,如果此值小于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
//被最长的替换为
//连续的序列。
#include <bits/stdc++.h>
using namespace std;
//用于返回要替换的索引0-
//用1来获得最长的连续
//1s的顺序。如果没有0-
//在数组中,然后返回-1。
int maxOnesIndex(bool arr1[], int n1){
   int i = 0;
   //用于存储左侧的计数
   //当前元素零的一侧
   int leftCnt1 = 0;
   //用来存储右边的数量
   //当前元素零的一侧
   int rightCnt1 = 0;
   //显示零的索引,最大数量
   //周围的人。
   int maxIndex1 = -1;
   //显示最近看到的零个元素的索引
   int lastInd1 = -1;
   //展会算的,如果在零指标
   //maxInd1被替换为一个。
   int maxCnt1 = 0;
   while (i < n1) {
      //用于保持递增计数,直到
      //当前元素是1
      if (arr1[i]) {
         rightCnt1++;
      }
      else {
         //已经观察到,如果当前零元素
         //不是第一个零元素,
         //然后数一
         //处替换零来获得
         //索引lastInd。更新maxCnt-
         //和maxIndex(如果需要)。
         if (lastInd1 != -1) {
            if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
               maxCnt1 = leftCnt1 + rightCnt1 + 1;
               maxIndex1 = lastInd1;
            }
         }
         lastInd1 = i;
         leftCnt1 = rightCnt1;
         rightCnt1 = 0;
      }
      i++;
   }
   //确定连续的数量
   //时的顺序
   //换成一个。
   if (lastInd1 != -1) {
      if (leftCnt1 + rightCnt1 + 1 > maxCnt1) {
         maxCnt1 = leftCnt1 + rightCnt1 + 1;
         maxIndex1 = lastInd1;
      }
   }
   return maxIndex1;
}
//驱动功能
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
猜你喜欢