Dada una array arr[] que consiste en N enteros positivos y algunos elementos como -1 , la tarea es encontrar el número más pequeño, digamos K , tal que al reemplazar todos los -1 en la array por K se minimice la máxima diferencia absoluta entre cualquier par de elementos adyacentes .
Ejemplos:
Entrada: arr[] = {-1, 10, -1, 12, -1}
Salida: 11
Explicación:
Considere el valor de K como 11. Ahora, reemplace todos los elementos de la array que tengan el valor -1 por el valor K(= 11 ) modifica la array a {11, 10, 11, 12, 11}. La máxima diferencia absoluta entre todos los elementos adyacentes es 1, que es el mínimo entre todos los valores posibles de K.Entrada: arr[] = {1, -1, 3, -1}
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado al iterar sobre todos los valores posibles de K desde 1 , verifique uno por uno qué valor de K da la diferencia absoluta máxima minimizada entre dos elementos adyacentes cualesquiera e imprima ese valor K .
Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de las siguientes observaciones:
- Si el valor absoluto de cualquier número, digamos X , debe minimizarse del conjunto de números, el promedio del elemento mínimo y máximo del conjunto de es el valor más óptimo para X que minimiza el valor absoluto.
- Por lo tanto, la idea es encontrar el valor mínimo y máximo de todos los elementos de la array que son adyacentes al elemento «-1» e imprimir el promedio de los dos números como el valor resultante de K.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos maxE como INT_MIN y minE como INT_MAX , para almacenar el elemento máximo y mínimo entre todos los valores posibles que son adyacentes a «-1» en la array.
- Recorra la array dada y realice los siguientes pasos:
- Si el elemento actual arr[i] es “-1” y el siguiente elemento no es “-1” , actualice el valor de maxE al máximo de maxE y arr[i + 1] y minE al mínimo de minE y arr[i + 1] .
- Si el elemento actual arr[i] no es “-1” y el siguiente elemento es “-1” , actualice el valor de maxE al máximo de maxE y arr[i] y minE al mínimo de minE y arr[ yo] .
- Después de completar los pasos anteriores, si el valor de maxE y minE no cambia, entonces todos los elementos de la array son «-1» , por lo tanto, imprima 0 como el valor resultante de K. De lo contrario, imprima el promedio de minE y maxE como el valor resultante de K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the value of K to
// minimize the value of maximum absolute
// difference between adjacent elements
void findMissingValue(int arr[], int N)
{
// Stores the maximum and minimum
// among array elements that are
// adjacent to "-1"
int minE = INT_MAX, maxE = INT_MIN;
// Traverse the given array arr[]
for (int i = 0; i < N - 1; i++) {
// If arr[i] is -1 & arr[i + 1]
// is not -1
if (arr[i] == -1
&& arr[i + 1] != -1) {
minE = min(minE, arr[i + 1]);
maxE = max(maxE, arr[i + 1]);
}
// If arr[i + 1] is -1 & arr[i]
// is not -1
if (arr[i] != -1
&& arr[i + 1] == -1) {
minE = min(minE, arr[i]);
maxE = max(maxE, arr[i]);
}
}
// If all array element is -1
if (minE == INT_MAX
and maxE == INT_MIN) {
cout << "0";
}
// Otherwise
else {
cout << (minE + maxE) / 2;
}
}
// Driver Code
int main()
{
int arr[] = { 1, -1, -1, -1, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
findMissingValue(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the value of K to
// minimize the value of maximum absolute
// difference between adjacent elements
public static void findMissingValue(int arr[], int N)
{
// Stores the maximum and minimum
// among array elements that are
// adjacent to "-1"
int minE = Integer.MAX_VALUE,
maxE = Integer.MIN_VALUE;
// Traverse the given array arr[]
for(int i = 0; i < N - 1; i++)
{
// If arr[i] is -1 & arr[i + 1]
// is not -1
if (arr[i] == -1 && arr[i + 1] != -1)
{
minE = Math.min(minE, arr[i + 1]);
maxE = Math.max(maxE, arr[i + 1]);
}
// If arr[i + 1] is -1 & arr[i]
// is not -1
if (arr[i] != -1 && arr[i + 1] == -1)
{
minE = Math.min(minE, arr[i]);
maxE = Math.max(maxE, arr[i]);
}
}
// If all array element is -1
if (minE == Integer.MAX_VALUE &&
maxE == Integer.MIN_VALUE)
{
System.out.println("0");
}
// Otherwise
else
{
System.out.println((minE + maxE) / 2);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, -1, -1, -1, 5 };
int N = arr.length;
findMissingValue(arr, N);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach
import sys
# Function to find the value of K to
# minimize the value of maximum absolute
# difference between adjacent elements
def findMissingValue(arr, N):
# Stores the maximum and minimum
# among array elements that are
# adjacent to "-1"
minE = sys.maxsize
maxE = -sys.maxsize - 1
# Traverse the given array arr[]
for i in range(N - 1):
# If arr[i] is -1 & arr[i + 1]
# is not -1
if (arr[i] == -1 and arr[i + 1] != -1):
minE = min(minE, arr[i + 1])
maxE = max(maxE, arr[i + 1])
# If arr[i + 1] is -1 & arr[i]
# is not -1
if (arr[i] != -1 and arr[i + 1] == -1):
minE = min(minE, arr[i])
maxE = max(maxE, arr[i])
# If all array element is -1
if (minE == sys.maxsize and maxE == -sys.maxsize-1):
print("0")
# Otherwise
else:
print((minE + maxE) // 2)
# Driver Code
if __name__ == '__main__':
arr = [1, -1, -1, -1, 5]
N = len(arr)
findMissingValue(arr, N)
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the value of K to
// minimize the value of maximum absolute
// difference between adjacent elements
public static void findMissingValue(int[] arr, int N)
{
// Stores the maximum and minimum
// among array elements that are
// adjacent to "-1"
int minE = Int32.MaxValue,
maxE = Int32.MinValue;
// Traverse the given array arr[]
for(int i = 0; i < N - 1; i++)
{
// If arr[i] is -1 & arr[i + 1]
// is not -1
if (arr[i] == -1 && arr[i + 1] != -1)
{
minE = Math.Min(minE, arr[i + 1]);
maxE = Math.Max(maxE, arr[i + 1]);
}
// If arr[i + 1] is -1 & arr[i]
// is not -1
if (arr[i] != -1 && arr[i + 1] == -1)
{
minE = Math.Min(minE, arr[i]);
maxE = Math.Max(maxE, arr[i]);
}
}
// If all array element is -1
if (minE == Int32.MaxValue &&
maxE == Int32.MinValue)
{
Console.WriteLine("0");
}
// Otherwise
else
{
Console.WriteLine((minE + maxE) / 2);
}
}
// Driver Code
public static void Main()
{
int[] arr = { 1, -1, -1, -1, 5 };
int N = arr.Length;
findMissingValue(arr, N);
}
}
// This code is contributed by rishavmahato348
Javascript
<script>
// JavaScript program for the above approach
// Function to find the value of K to
// minimize the value of maximum absolute
// difference between adjacent elements
function findMissingValue(arr, N)
{
// Stores the maximum and minimum
// among array elements that are
// adjacent to "-1"
let minE = Number.MAX_VALUE,
maxE = Number.MIN_VALUE;
// Traverse the given array arr[]
for(let i = 0; i < N - 1; i++)
{
// If arr[i] is -1 & arr[i + 1]
// is not -1
if (arr[i] == -1 && arr[i + 1] != -1)
{
minE = Math.min(minE, arr[i + 1]);
maxE = Math.max(maxE, arr[i + 1]);
}
// If arr[i + 1] is -1 & arr[i]
// is not -1
if (arr[i] != -1 && arr[i + 1] == -1)
{
minE = Math.min(minE, arr[i]);
maxE = Math.max(maxE, arr[i]);
}
}
// If all array element is -1
if (minE == Number.MAX_VALUE &&
maxE == Number.MIN_VALUE)
{
document.write("0");
}
// Otherwise
else
{
document.write((minE + maxE) / 2);
}
}
// Driver Code
let arr = [ 1, -1, -1, -1, 5 ];
let N = arr.length;
findMissingValue(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA