Dada una array de n enteros, para cada elemento, imprima la distancia al cero más cercano. La array tiene un mínimo de 1 cero en ella.
Ejemplos:
Input: 5 6 0 1 -2 3 4 Output: 2 1 0 1 2 3 4 Explanation : The nearest 0(indexed 2) to 5(indexed 0) is at a distance of 2, so we print 2. Same is done for the rest of elements.
Enfoque ingenuo:
Un enfoque ingenuo es, para cada elemento, deslizar hacia la izquierda y encontrar el 0 más cercano y nuevamente deslizar hacia la derecha para encontrar el cero más cercano, si lo hay, e imprimir el mínimo de ambas distancias. Será eficiente en el espacio, pero la complejidad del tiempo será alta, ya que tenemos que iterar para cada elemento hasta que encontremos el 0 y, en el peor de los casos, es posible que no lo encontremos en una dirección.
Complejidad de tiempo : O(n^2)
Espacio auxiliar: O(1)
Enfoque eficiente:
Un enfoque eficiente es utilizar la técnica de la ventana deslizante dos veces. Uno va de derecha a izquierda y el otro de izquierda a derecha.
Inicialice ans[0] con un valor máximo. Iterar sobre la array de izquierda a derecha. Si el valor en la posición actual es 0, establezca la distancia en 0; de lo contrario, aumente la distancia en 1. En cada paso, escriba el valor de la distancia en la array de respuesta.
Haz lo mismo pero de derecha a izquierda. Esto encontrará el cero más cercano a la derecha. Ahora debemos almacenar el mínimo del valor actual de la distancia y el valor que ya está en la array de respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find closest 0 for every element
#include <bits/stdc++.h>
using namespace std;
// Print the distance with zeroes of every element
void print_distance(int arr[], int n)
{
// initializes an array of size n with 0
int ans[n];
memset(arr, 0, sizeof(arr[0]));
// if first element is 0 then the distance
// will be 0
if (arr[0] == 0)
ans[0] = 0;
else
ans[0] = INT_MAX; // if not 0 then initialize
// with a maximum value
// traverse in loop from 1 to n and store
// the distance from left
for (int i = 1; i < n; ++i) {
// add 1 to the distance from previous one
ans[i] = ans[i - 1] + 1;
// if the present element is 0 then distance
// will be 0
if (arr[i] == 0)
ans[i] = 0;
}
// if last element is zero then it will be 0 else
// let the answer be what was found when traveled
// from left to right
if (arr[n - 1] == 0)
ans[n - 1] = 0;
// traverse from right to left and store the minimum
// of distance if found from right to left or left
// to right
for (int i = n - 2; i >= 0; --i) {
// store the minimum of distance from left to
// right or right to left
ans[i] = min(ans[i], ans[i + 1] + 1);
// if it is 0 then minimum will always be 0
if (arr[i] == 0)
ans[i] = 0;
}
// print the answer array
for (int i = 0; i < n; ++i)
cout << ans[i] << " ";
}
// driver program to test the above function
int main()
{
int a[] = { 2, 1, 0, 3, 0, 0, 3, 2, 4 };
int n = sizeof(a) / sizeof(a[0]);
print_distance(a, n);
return 0;
}
Java
// Java program to find closest
// 0 for every element
import java.util.Arrays;
class GFG
{
// Print the distance with zeroes of every element
static void print_distance(int arr[], int n)
{
// initializes an array of size n with 0
int ans[]=new int[n];
Arrays.fill(ans,0);
// if first element is 0 then the distance
// will be 0
if (arr[0] == 0)
ans[0] = 0;
// if not 0 then initialize
// with a maximum value
else
ans[0] = +2147483647;
// traverse in loop from 1 to n and store
// the distance from left
for (int i = 1; i < n; ++i)
{
// add 1 to the distance
// from previous one
ans[i] = ans[i - 1] + 1;
// if the present element is
// 0 then distance will be 0
if (arr[i] == 0)
ans[i] = 0;
}
// if last element is zero
// then it will be 0 else
// let the answer be what was
// found when traveled
// from left to right
if (arr[n - 1] == 0)
ans[n - 1] = 0;
// traverse from right to
// left and store the minimum
// of distance if found from
// right to left or left
// to right
for (int i = n - 2; i >= 0; --i)
{
// store the minimum of distance
// from left to right or right to left
ans[i] = Math.min(ans[i], ans[i + 1] + 1);
// if it is 0 then minimum
// will always be 0
if (arr[i] == 0)
ans[i] = 0;
}
// print the answer array
for (int i = 0; i < n; ++i)
System.out.print(ans[i] + " ");
}
// Driver code
public static void main (String[] args)
{
int a[] = { 2, 1, 0, 3, 0, 0, 3, 2, 4 };
int n = a.length;
print_distance(a, n);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find closest 0 # for every element # Print the distance with zeroes of # every element def print_distance(arr, n): # initializes an array of size n with 0 ans = [0 for i in range(n)] # if first element is 0 then the # distance will be 0 if (arr[0] == 0): ans[0] = 0 else: ans[0] = 10**9 # if not 0 then initialize # with a maximum value # traverse in loop from 1 to n and # store the distance from left for i in range(1, n): # add 1 to the distance from # previous one ans[i] = ans[i - 1] + 1 # if the present element is 0 then # distance will be 0 if (arr[i] == 0): ans[i] = 0 # if last element is zero then it will be 0 # else let the answer be what was found when # traveled from left to right if (arr[n - 1] == 0): ans[n - 1] = 0 # traverse from right to left and store # the minimum of distance if found from # right to left or left to right for i in range(n - 2, -1, -1): # store the minimum of distance from # left to right or right to left ans[i] = min(ans[i], ans[i + 1] + 1) # if it is 0 then minimum will # always be 0 if (arr[i] == 0): ans[i] = 0 # print the answer array for i in ans: print(i, end = " ") # Driver Code a = [2, 1, 0, 3, 0, 0, 3, 2, 4] n = len(a) print_distance(a, n) # This code is contributed # by Mohit Kumar
C#
// C# program to find closest
// 0 for every element
using System;
class GFG
{
// Print the distance with zeroes of every element
static void print_distance(int []arr, int n)
{
// initializes an array of size n with 0
int []ans=new int[n];
for(int i = 0; i < n; i++)
ans[i] = 0;
// if first element is 0 then the distance
// will be 0
if (arr[0] == 0)
ans[0] = 0;
// if not 0 then initialize
// with a maximum value
else
ans[0] = +2147483646;
// traverse in loop from 1 to n and store
// the distance from left
for (int i = 1; i < n; ++i)
{
// add 1 to the distance
// from previous one
ans[i] = ans[i - 1] + 1;
// if the present element is
// 0 then distance will be 0
if (arr[i] == 0)
ans[i] = 0;
}
// if last element is zero
// then it will be 0 else
// let the answer be what was
// found when traveled
// from left to right
if (arr[n - 1] == 0)
ans[n - 1] = 0;
// traverse from right to
// left and store the minimum
// of distance if found from
// right to left or left
// to right
for (int i = n - 2; i >= 0; --i)
{
// store the minimum of distance
// from left to right or right to left
ans[i] = Math.Min(ans[i], ans[i + 1] + 1);
// if it is 0 then minimum
// will always be 0
if (arr[i] == 0)
ans[i] = 0;
}
// print the answer array
for (int i = 0; i < n; ++i)
Console.Write(ans[i] + " ");
}
// Driver code
public static void Main (String[] args)
{
int []a = { 2, 1, 0, 3, 0, 0, 3, 2, 4 };
int n = a.Length;
print_distance(a, n);
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
// PHP program to find closest 0
// for every element
// Print the distance with zeroes
// of every element
function print_distance($arr, $n)
{
// initializes an array of size n with 0
$ans[$n] = array();
$ans = array_fill(0, $n, true);
// if first element is 0 then the
// distance will be 0
if ($arr[0] == 0)
$ans[0] = 0;
else
$ans[0] = PHP_INT_MAX; // if not 0 then initialize
// with a maximum value
// traverse in loop from 1 to n and
// store the distance from left
for ( $i = 1; $i < $n; ++$i)
{
// add 1 to the distance from
// previous one
$ans[$i] = $ans[$i - 1] + 1;
// if the present element is 0
// then distance will be 0
if ($arr[$i] == 0)
$ans[$i] = 0;
}
// if last element is zero then it will
// be 0 else let the answer be what was
// found when traveled from left to right
if ($arr[$n - 1] == 0)
$ans[$n - 1] = 0;
// traverse from right to left and store
// the minimum of distance if found from
// right to left or left to right
for ($i = $n - 2; $i >= 0; --$i)
{
// store the minimum of distance from
// left to right or right to left
$ans[$i] = min($ans[$i], $ans[$i + 1] + 1);
// if it is 0 then minimum will
// always be 0
if ($arr[$i] == 0)
$ans[$i] = 0;
}
// print the answer array
for ($i = 0; $i < $n; ++$i)
echo $ans[$i] , " ";
}
// Driver Code
$a = array( 2, 1, 0, 3, 0, 0, 3, 2, 4 );
$n = sizeof($a);
print_distance($a, $n);
// This code is contributed by Sachin
?>
Javascript
<script>
// javascript program to find closest
// 0 for every element
// Print the distance with zeroes of every element
function print_distance(arr , n)
{
// initializes an array of size n with 0
var ans = Array(n).fill(0);
// if first element is 0 then the distance
// will be 0
if (arr[0] == 0)
ans[0] = 0;
// if not 0 then initialize
// with a maximum value
else
ans[0] = +2147483647;
// traverse in loop from 1 to n and store
// the distance from left
for (i = 1; i < n; ++i) {
// add 1 to the distance
// from previous one
ans[i] = ans[i - 1] + 1;
// if the present element is
// 0 then distance will be 0
if (arr[i] == 0)
ans[i] = 0;
}
// if last element is zero
// then it will be 0 else
// let the answer be what was
// found when traveled
// from left to right
if (arr[n - 1] == 0)
ans[n - 1] = 0;
// traverse from right to
// left and store the minimum
// of distance if found from
// right to left or left
// to right
for (i = n - 2; i >= 0; --i) {
// store the minimum of distance
// from left to right or right to left
ans[i] = Math.min(ans[i], ans[i + 1] + 1);
// if it is 0 then minimum
// will always be 0
if (arr[i] == 0)
ans[i] = 0;
}
// print the answer array
for (i = 0; i < n; ++i)
document.write(ans[i] + " ");
}
// Driver code
var a = [ 2, 1, 0, 3, 0, 0, 3, 2, 4 ];
var n = a.length;
print_distance(a, n);
// This code is contributed by Rajput-Ji
</script>
Producción
0 1 0 1 0 0 1 2 3
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Raja Vikramaditya . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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