查找索引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 };
//boolarr1[]={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