# 查找索引 0 替換為 1，以獲得二進制數組中最長的連續序列 1 > 原文： [https://www.geeksforgeeks.org/find-index-0-replaced-1-get-longest-continuous-sequence-1s-binary-array/](https://www.geeksforgeeks.org/find-index-0-replaced-1-get-longest-continuous-sequence-1s-binary-array/) 給定一個 0 和 1 的數組，找到 0 的位置要替換為 1，以獲得最長的 1 連續序列。 預期時間復雜度為`O(n)`，輔助空間為`O(1)`。 **例如**： ``` Input: arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1} Output: Index 9 Assuming array index starts from 0, replacing 0 with 1 at index 9 causes the maximum continuous sequence of 1s. Input: arr[] = {1, 1, 1, 1, 0} Output: Index 4 ``` **我們強烈建議最小化瀏覽器，然后自己嘗試。** 一個**簡單解決方案**是遍歷該數組，對于每個 0，計算數組兩側的 1 的數量。 跟蹤任意 0 的最大計數。最后返回 0 的索引，最大索引數為 1。 該解決方案的時間復雜度為`O(n^2)`。 使用**有效解決方案**可以在`O(n)`時間內解決問題。 這個想法是要跟蹤三個索引，即當前索引（`curr`），先前的零索引（`prev_zero`）和先前的零索引（`prev_prev_zero`）。 遍歷數組，如果當前元素為 0，則計算`curr`與`prev_prev_zero`之間的差（該差減 1 是`prev_zero`周圍的 1 的數量）。 如果*當前值*與`prev_prev_zero`之間的差值到目前為止尚未達到最大值，則更新最大值。 最后返回具有最大差異的`prev_zero`的索引。 以下是上述算法的實現。 ## C++ ```cpp // C++ program to find Index of 0 to be replaced with 1 to get // longest continuous sequence of 1s in a binary array #include<iostream> using namespace std; // 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 arr[], int n) { ????int max_count = 0;? // for maximum number of 1 around a zero ????int max_index;? // for storing result ????int prev_zero = -1;? // index of previous zero ????int prev_prev_zero = -1; // index of previous to previous zero ????// Traverse the input array ????for (int curr=0; curr<n; ++curr) ????{ ????????// If current element is 0, then calculate the difference ????????// between curr and prev_prev_zero ????????if (arr[curr] == 0) ????????{ ????????????// Update result if count of 1s around prev_zero is more ????????????if (curr - prev_prev_zero > max_count) ????????????{ ????????????????max_count = curr - prev_prev_zero; ????????????????max_index = prev_zero; ????????????} ????????????// Update for next iteration ????????????prev_prev_zero = prev_zero; ????????????prev_zero = curr; ????????} ????} ????// Check for the last encountered zero ????if (n-prev_prev_zero > max_count) ???????max_index = prev_zero; ????return max_index; } // Driver program int main() { ????bool arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1}; ????int n = sizeof(arr)/sizeof(arr[0]); ????cout << "Index of 0 to be replaced is " ?????????<< maxOnesIndex(arr, n); ????return 0; } ``` ## Java ```java // Java program to find Index of 0 to be replaced with 1 to get // longest continuous sequence of 1s in a binary array import java.io.*; class Binary? {???? ????// 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\. ????static int maxOnesIndex(int arr[], int n) ????{ ????????int max_count = 0;? // for maximum number of 1 around a zero ????????int max_index=0;? // for storing result ????????int prev_zero = -1;? // index of previous zero ????????int prev_prev_zero = -1; // index of previous to previous zero ????????// Traverse the input array ????????for (int curr=0; curr<n; ++curr) ????????{ ????????????// If current element is 0, then calculate the difference ????????????// between curr and prev_prev_zero ????????????if (arr[curr] == 0) ????????????{ ????????????????// Update result if count of 1s around prev_zero is more ????????????????if (curr - prev_prev_zero > max_count) ????????????????{ ????????????????????max_count = curr - prev_prev_zero; ????????????????????max_index = prev_zero; ????????????????} ????????????????// Update for next iteration ????????????????prev_prev_zero = prev_zero; ????????????????prev_zero = curr; ????????????} ????????} ????????// Check for the last encountered zero ????????if (n-prev_prev_zero > max_count) ????????????max_index = prev_zero; ????????return max_index; ????} ????// Driver program to test above function ????public static void main(String[] args) ????{ ????????int arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1}; ????????int n = arr.length; ????????System.out.println("Index of 0 to be replaced is "+? ???????????????????????????maxOnesIndex(arr, n));???????? ????} } /* This code is contributed by Devesh Agrawal */ ``` ## Python3 ```py # Python program to find Index # of 0 to be replaced with 1 to get # longest continuous sequence # of 1s in a binary array # 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\. def maxOnesIndex(arr,n): ????# for maximum number of 1 around a zero ????max_count = 0 ????# for storing result?? ????max_index =0?? ????# index of previous zero ????prev_zero = -1?? ????# index of previous to previous zero ????prev_prev_zero = -1? ????# Traverse the input array ????for curr in range(n): ????????# If current element is 0, ????????# then calculate the difference ????????# between curr and prev_prev_zero ????????if (arr[curr] == 0): ????????????# Update result if count of ????????????# 1s around prev_zero is more ????????????if (curr - prev_prev_zero > max_count): ????????????????max_count = curr - prev_prev_zero ????????????????max_index = prev_zero ????????????# Update for next iteration ????????????prev_prev_zero = prev_zero ????????????prev_zero = curr ????# Check for the last encountered zero ????if (n-prev_prev_zero > max_count): ????????max_index = prev_zero ????return max_index # Driver program arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1] n = len(arr) print("Index of 0 to be replaced is ", ????maxOnesIndex(arr, n)) # This code is contributed # by Anant Agarwal. ``` ## C# ```cs // C# program to find Index of 0 to be replaced // with 1 to get longest continuous sequence of // 1s in a binary array using System; class GFG { ????// 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\. ????static int maxOnesIndex(int []arr, int n) ????{ ????????// for maximum number of 1 around a zero ????????int max_count = 0;? ????????// for storing result ????????int max_index = 0;? ????????// index of previous zero ????????int prev_zero = -1;? ????????// index of previous to previous zero ????????int prev_prev_zero = -1;? ????????// Traverse the input array ????????for (int curr = 0; curr < n; ++curr) ????????{ ????????????// If current element is 0, then? ????????????// calculate the difference ????????????// between curr and prev_prev_zero ????????????if (arr[curr] == 0) ????????????{ ????????????????// Update result if count of 1s? ????????????????// around prev_zero is more ????????????????if (curr - prev_prev_zero > max_count) ????????????????{ ????????????????????max_count = curr - prev_prev_zero; ????????????????????max_index = prev_zero; ????????????????} ????????????????// Update for next iteration ????????????????prev_prev_zero = prev_zero; ????????????????prev_zero = curr; ????????????} ????????} ????????// Check for the last encountered zero ????????if (n-prev_prev_zero > max_count) ????????????max_index = prev_zero; ????????return max_index; ????} ????// Driver program to test above function ????public static void Main() ????{ ????????int []arr = {1, 1, 0, 0, 1, 0, 1, 1, 1, ?????????????????????????????????????0, 1, 1, 1}; ????????int n = arr.Length; ????Console.Write("Index of 0 to be replaced is " ?????????????????????????+ maxOnesIndex(arr, n));????? ????} } // This code is contributed by nitin mittal. ``` ## PHP ```php <?php // PHP program to find Index of 0 to be? // replaced with 1 to get longest continuous? // sequence of 1s in a binary array // 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\. function maxOnesIndex( $arr, $n) { ????$max_count = 0; // for maximum number of? ????????????????????// 1 around a zero ????$max_index; // for storing result ????$prev_zero = -1; // index of previous zero ????$prev_prev_zero = -1; // index of previous to ??????????????????????????// previous zero ????// Traverse the input array ????for ($curr = 0; $curr < $n; ++$curr) ????{ ????????// If current element is 0, then? ????????// calculate the difference ????????// between curr and prev_prev_zero ????????if ($arr[$curr] == 0) ????????{ ????????????// Update result if count of 1s? ????????????// around prev_zero is more ????????????if ($curr - $prev_prev_zero > $max_count) ????????????{ ????????????????$max_count = $curr - $prev_prev_zero; ????????????????$max_index = $prev_zero; ????????????} ????????????// Update for next iteration ????????????$prev_prev_zero = $prev_zero; ????????????$prev_zero = $curr; ????????} ????} ????// Check for the last encountered zero ????if ($n - $prev_prev_zero > $max_count) ????$max_index = $prev_zero; ????return $max_index; } // Driver Code $arr = array(1, 1, 0, 0, 1, 0, 1,? ?????????????1, 1, 0, 1, 1, 1); $n = sizeof($arr); echo "Index of 0 to be replaced is ", ??????maxOnesIndex($arr, $n); // This code is contributed by ajit ?> ``` **輸出**： ``` Index of 0 to be replaced is 9 ``` **時間復雜度**： `O(n)` **輔助空間**： `O(1)`