Dada una array de 0 y 1, encuentre la posición de 0 para ser reemplazada por 1 para obtener la secuencia continua más larga de 1. La complejidad de tiempo esperada es O(n) y el espacio auxiliar es O(1).
Ejemplo:
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
Recomendamos encarecidamente minimizar el navegador y probarlo usted mismo primero.
Una solución simple es atravesar la array, por cada 0, cuente el número de 1 en ambos lados de la misma. Realice un seguimiento del recuento máximo para cualquier 0. Finalmente, devuelva el índice del 0 con el número máximo de 1 a su alrededor. La complejidad temporal de esta solución es O(n 2 ).
Utilizando una Solución Eficiente , el problema puede resolverse en tiempo O(n). La idea es realizar un seguimiento de tres índices, el índice actual ( curr ), el índice cero anterior ( prev_zero ) y el índice cero anterior al anterior ( prev_prev_zero ). Recorra la array, si el elemento actual es 0, calcule la diferencia entre curr y prev_prev_zero (esta diferencia menos uno es el número de 1 alrededor de prev_zero). Si la diferencia entre curr y prev_prev_zero es mayor que el máximo hasta el momento, actualice el máximo. Finalmente, devuelva el índice de prev_zero con la diferencia máxima.
Las siguientes son las implementaciones del algoritmo anterior.
C++
// 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 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
# 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#
// 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 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
?>
Javascript
<script>
// Javascript 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)
{
// for maximum number of 1 around a zero
let max_count = 0;
// for storing result
let max_index = 0;
// index of previous zero
let prev_zero = -1;
// index of previous to previous zero
let prev_prev_zero = -1;
// Traverse the input array
for(let 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
let arr = [ 1, 1, 0, 0, 1, 0, 1,
1, 1, 0, 1, 1, 1 ];
let n = arr.length;
document.write("Index of 0 to be replaced is " +
maxOnesIndex(arr, n));
// This code is contributed by divyesh072019
</script>
Producción
Index of 0 to be replaced is 9
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA