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

  • Z时代
  • 2024-01-10
  • 分类：综合

概念

对于给定的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

以上是 查找索引0替换为1以获取二进制数组中最长的连续1序列-C ++中的Set-2 的全部内容， 来源链接： utcz.com/z/321827.html

回到顶部