資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
