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