数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在二进制数组中查找需要替换为 1 的 0 的索引以获得最长的连续 1 序列 - C++ 中的 Set-2
概念
对于给定的 0 和 1 数组，确定将 0 替换为 1 以获得最大连续 1 序列的位置。在这种情况下，预期时间复杂度为 O(n)，辅助空间为 O(1)。
输入
arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}输出
Index 10
假设数组索引从 0 开始，在
索引 10 处将 0 替换为 1 会导致最长的连续 1 序列。
输入
arr[] = {1, 1, 1, 1, 1, 0}输出
Index 5
方法
使用零两侧的 1 的计数 -
现在，这个概念是在每个零的两侧计算 1 的数量。在这里，所需索引被视为周围有最大数量的 1 的零的索引。以下变量是针对此目的实现的 -
- leftCnt - 用于存储当前考虑的零元素左侧 1 的数量。
- rightCnt - 用于存储当前考虑的零元素右侧 1 的数量。
- maxIndex - 被视为周围有最大数量的 1 的零的索引。
- lastInd - 被视为看到的最后一个零元素的索引
- maxCnt - 被视为如果将索引 maxInd 处的零替换为 1，则 1 的数量。
现在给出以下过程细节 -
在输入数组中存在 1 时保持 rightCnt 的递增。假设下一个零位于索引 i 处。
验证此零元素是否为第一个零元素。现在，如果 lastInd 不持有任何有效的索引值，则将其视为第一个零元素。
因此，在这种情况下，使用 i 更新 lastInd。目前，rightCnt 的值为该零左侧的零的数量。
因此，leftCnt 等于 rightCnt，然后再次确定 rightCnt 的值。已经观察到，如果当前零元素不是第一个零，则索引 lastInd 处存在的零周围的 1 的数量由 leftCnt + rightCnt 提供。
现在，如果此值小于 maxCnt 当前持有的值，则 maxCnt 将接受值 leftCnt + rightCnt + 1 并且 maxIndex = lastInd。
目前，rightCnt 将变为索引 i 处零的 leftCnt，lastInd 将等于 i。现在再次确定 rightCnt 的值，将 1 的数量与 maxCnt 进行比较，并相应地更新 maxCnt 和 maxIndex。
我们必须对数组的每个后续零元素重复此过程。
已经观察到，lastInd 存储计算当前 leftCnt 和 rightCnt 的零的索引。
最后，要替换为 1 的零的所需索引存储在 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
100 次查看
