Dada una array, encuentre la diferencia máxima entre sus dos elementos consecutivos en su forma ordenada.
Ejemplos:
Input: arr[] = {1, 10, 5}
Output: 5
Sorted array would be {1, 5, 10} and
maximum adjacent difference would be
10 - 5 = 5
Input: arr[] = {2, 4, 8, 11}
Output: 4
Solución ingenua:
Primero ordene la array, luego atraviésela y realice un seguimiento de la diferencia máxima entre los elementos adyacentes.
La complejidad temporal de este método es O(nlogn).
Solución eficiente:
esta solución se basa en la idea de la clasificación por casilleros . No es necesario ordenar la array, solo tiene que llenar los cubos y realizar un seguimiento del valor máximo y mínimo de cada cubo. Si se encuentra un balde vacío, el espacio máximo sería la diferencia entre el valor máximo del balde anterior y el valor mínimo del balde siguiente .
Como queremos casi ordenarlos para que podamos tener la máxima brecha. También para cualquier i-ésimo elemento, el valor de (arr[i]-min_value)/(max_value-min_value) sigue aumentando a medida que arr[i] sigue aumentando y este valor siempre varía de 0 a 1. Como queremos poner los resultados ordenados en cubo de tamaño n. Multiplicamos este valor por (n-1), por lo tanto, hacemos una variable delta = (max_value – min_value)/(n-1) . Ahora, en maxBucket o minBucket, todo el valor en cualquier índice j antes del índice cualquier i siempre será menor que el valor en el índice i, minBucket[j]<minBucket[i] para j<i. Es posible que dos arr[i] diferentes puedan tener el mismo valor de (arr[i]-min_value)/delta , por lo tanto, estamos creando 2 cubos diferentes maxBucket y minBucket.
Como hemos encontrado la diferencia máxima entre valores consecutivos , debemos considerar el valor máximo posible hasta el índice anterior como prev_val y minBucket[i] para el índice actual i, y ans será el máximo de ans y minBucket[i]-prev_val.
Resolvamos el ejemplo anterior con este enfoque.
Ejemplo de trabajo:
Entrada : arr[] = {1, 10, 5}
Salida: 5
Paso 1 : Encuentra max_val y min_val
valor_máximo = 10, valor_mínimo = 1
Paso 2 : Calcular delta
delta = (valor_máximo – valor_mínimo)/(n-1)
delta = (10-1)/(3-1) = 4,5
Paso 3: inicialice depósitos, maxBucket ={INT_MIN}, minBucket={INT_MAX}
Paso 4 : para cualquier índice i, calcule el índice arr[i] en el depósito y actualícelo en los depósitos,
en = (arr[i]-min_val)/delta
maxBucket[en]=max(maxBucket[en],arr[i])
minBucket[en]=min(minBucket[en],arr[i])
para todos los índices en arr in los valores son => 0,2,0
maxCucket=[5,INT_MIN,10]
minCubo=[1,INT_MAX,10]
Paso 5 : Por lo tanto, ans es el máximo de minBucket[i]-(máximo del valor hasta el índice anterior)
en este caso para i=2: max_gap = max(max_gap,minBucket[2] – max(maxBucket[1],maxBucket[0]))
espacio_máximo = 10-5=5
Esto es solo para presentar el concepto, todas las demás validaciones básicas están en el código principal.
A continuación se muestra el código para el enfoque anterior:
C++
// CPP program to find maximum adjacent difference
// between two adjacent after sorting.
#include <bits/stdc++.h>
using namespace std;
int maxSortedAdjacentDiff(int* arr, int n)
{
// Find maximum and minimum in arr[]
int maxVal = arr[0], minVal = arr[0];
for (int i = 1; i < n; i++) {
maxVal = max(maxVal, arr[i]);
minVal = min(minVal, arr[i]);
}
// Arrays to store maximum and minimum values
// in n-1 buckets of differences.
int maxBucket[n - 1];
int minBucket[n - 1];
fill_n(maxBucket, n - 1, INT_MIN);
fill_n(minBucket, n - 1, INT_MAX);
// Expected gap for every bucket.
float delta = (float)(maxVal - minVal) / (float)(n - 1);
// Traversing through array elements and
// filling in appropriate bucket if bucket
// is empty. Else updating bucket values.
for (int i = 0; i < n; i++) {
if (arr[i] == maxVal || arr[i] == minVal)
continue;
// Finding index of bucket.
int index = (float)(floor(arr[i] - minVal) / delta);
maxBucket[index] = max(maxBucket[index], arr[i]);
minBucket[index] = min(minBucket[index], arr[i]);
}
// Finding maximum difference between maximum value
// of previous bucket minus minimum of current bucket.
int prev_val = minVal;
int max_gap = 0;
for (int i = 0; i < n - 1; i++) {
if (minBucket[i] == INT_MAX)
continue;
max_gap = max(max_gap, minBucket[i] - prev_val);
prev_val = maxBucket[i];
}
max_gap = max(max_gap, maxVal - prev_val);
return max_gap;
}
int main()
{
int arr[] = { 1, 10, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxSortedAdjacentDiff(arr, n) << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
// Java program to find maximum adjacent difference
// between two adjacent after sorting.
class GFG {
static int maxSortedAdjacentDiff(int[] arr, int n)
{
// Find maximum and minimum in arr[]
int maxVal = arr[0];
int minVal = arr[0];
for (int i = 1; i < n; i++) {
maxVal = Math.max(maxVal, arr[i]);
minVal = Math.min(minVal, arr[i]);
}
// Arrays to store maximum and minimum values
// in n-1 buckets of differences.
int maxBucket[] = new int[n - 1];
int minBucket[] = new int[n - 1];
Arrays.fill(maxBucket, 0, n - 1, Integer.MIN_VALUE);
Arrays.fill(minBucket, 0, n - 1, Integer.MAX_VALUE);
// Expected gap for every bucket.
float delta
= (float)(maxVal - minVal) / (float)(n - 1);
// Traversing through array elements and
// filling in appropriate bucket if bucket
// is empty. Else updating bucket values.
for (int i = 0; i < n; i++) {
if (arr[i] == maxVal || arr[i] == minVal) {
continue;
}
// Finding index of bucket.
int index = (int)(Math.round((arr[i] - minVal)
/ delta));
// Filling/Updating maximum value of bucket
if (maxBucket[index] == Integer.MIN_VALUE) {
maxBucket[index] = arr[i];
}
else {
maxBucket[index]
= Math.max(maxBucket[index], arr[i]);
}
// Filling/Updating minimum value of bucket
if (minBucket[index] == Integer.MAX_VALUE) {
minBucket[index] = arr[i];
}
else {
minBucket[index]
= Math.min(minBucket[index], arr[i]);
}
}
// Finding maximum difference between maximum value
// of previous bucket minus minimum of current
// bucket.
int prev_val = minVal;
int max_gap = 0;
for (int i = 0; i < n - 1; i++) {
if (minBucket[i] == Integer.MAX_VALUE) {
continue;
}
max_gap = Math.max(max_gap,
minBucket[i] - prev_val);
prev_val = maxBucket[i];
}
max_gap = Math.max(max_gap, maxVal - prev_val);
return max_gap;
}
// Driver program to run the case
public static void main(String[] args)
{
int arr[] = { 1, 10, 5 };
int n = arr.length;
System.out.println(maxSortedAdjacentDiff(arr, n));
}
}
Python3
# Python3 program to find maximum adjacent
# difference between two adjacent after sorting.
def maxSortedAdjacentDiff(arr, n):
# Find maximum and minimum in arr[]
maxVal, minVal = arr[0], arr[0]
for i in range(1, n):
maxVal = max(maxVal, arr[i])
minVal = min(minVal, arr[i])
# Arrays to store maximum and minimum
# values in n-1 buckets of differences.
maxBucket = [INT_MIN] * (n - 1)
minBucket = [INT_MAX] * (n - 1)
# Expected gap for every bucket.
delta = (maxVal - minVal) // (n - 1)
# Traversing through array elements and
# filling in appropriate bucket if bucket
# is empty. Else updating bucket values.
for i in range(0, n):
if arr[i] == maxVal or arr[i] == minVal:
continue
# Finding index of bucket.
index = (arr[i] - minVal) // delta
# Filling/Updating maximum value
# of bucket
if maxBucket[index] == INT_MIN:
maxBucket[index] = arr[i]
else:
maxBucket[index] = max(maxBucket[index],
arr[i])
# Filling/Updating minimum value of bucket
if minBucket[index] == INT_MAX:
minBucket[index] = arr[i]
else:
minBucket[index] = min(minBucket[index],
arr[i])
# Finding maximum difference between
# maximum value of previous bucket
# minus minimum of current bucket.
prev_val, max_gap = minVal, 0
for i in range(0, n - 1):
if minBucket[i] == INT_MAX:
continue
max_gap = max(max_gap,
minBucket[i] - prev_val)
prev_val = maxBucket[i]
max_gap = max(max_gap, maxVal - prev_val)
return max_gap
# Driver Code
if __name__ == "__main__":
arr = [1, 10, 5]
n = len(arr)
INT_MIN, INT_MAX = float('-inf'), float('inf')
print(maxSortedAdjacentDiff(arr, n))
# This code is contributed by Rituraj Jain
C#
// C# program to find maximum
// adjacent difference between
// two adjacent after sorting.
using System;
using System.Linq;
class GFG
{
static int maxSortedAdjacentDiff(int[] arr,
int n)
{
// Find maximum and minimum in arr[]
int maxVal = arr[0];
int minVal = arr[0];
for (int i = 1; i < n; i++)
{
maxVal = Math.Max(maxVal, arr[i]);
minVal = Math.Min(minVal, arr[i]);
}
// Arrays to store maximum and
// minimum values in n-1 buckets
// of differences.
int []maxBucket = new int[n - 1];
int []minBucket = new int[n - 1];
maxBucket = maxBucket.Select(i => int.MinValue).ToArray();
minBucket = minBucket.Select(i => int.MaxValue).ToArray();
// maxBucket.Fill(int.MinValue);
// Arrays.fill(minBucket, 0, n - 1, Integer.MAX_VALUE);
// Expected gap for every bucket.
float delta = (float) (maxVal - minVal) /
(float) (n - 1);
// Traversing through array elements and
// filling in appropriate bucket if bucket
// is empty. Else updating bucket values.
for (int i = 0; i < n; i++)
{
if (arr[i] == maxVal || arr[i] == minVal)
{
continue;
}
// Finding index of bucket.
int index = (int) (Math.Round((arr[i] -
minVal) / delta));
// Filling/Updating maximum value of bucket
if (maxBucket[index] == int.MinValue)
{
maxBucket[index] = arr[i];
}
else
{
maxBucket[index] = Math.Max(maxBucket[index],
arr[i]);
}
// Filling/Updating minimum value of bucket
if (minBucket[index] == int.MaxValue)
{
minBucket[index] = arr[i];
}
else
{
minBucket[index] = Math.Min(minBucket[index],
arr[i]);
}
}
// Finding maximum difference between
// maximum value of previous bucket
// minus minimum of current bucket.
int prev_val = minVal;
int max_gap = 0;
for (int i = 0; i < n - 1; i++)
{
if (minBucket[i] == int.MaxValue)
{
continue;
}
max_gap = Math.Max(max_gap, minBucket[i] -
prev_val);
prev_val = maxBucket[i];
}
max_gap = Math.Max(max_gap, maxVal -
prev_val);
return max_gap;
}
// Driver Code
public static void Main()
{
int []arr = {1, 10, 5};
int n = arr.Length;
Console.Write(maxSortedAdjacentDiff(arr, n));
}
}
// This code contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find maximum adjacent difference
// between two adjacent after sorting.
function maxSortedAdjacentDiff(arr, n)
{
// Find maximum and minimum in arr[]
var maxVal = arr[0], minVal = arr[0];
for (var i = 1; i < n; i++) {
maxVal = Math.max(maxVal, arr[i]);
minVal = Math.min(minVal, arr[i]);
}
// Arrays to store maximum and minimum values
// in n-1 buckets of differences.
var maxBucket = Array(n-1).fill(-1000000000);
var minBucket = Array(n-1).fill(1000000000);
// Expected gap for every bucket.
var delta = (maxVal - minVal) / (n - 1);
// Traversing through array elements and
// filling in appropriate bucket if bucket
// is empty. Else updating bucket values.
for (var i = 0; i < n; i++) {
if (arr[i] == maxVal || arr[i] == minVal)
continue;
// Finding index of bucket.
var index = Math.floor((arr[i] - minVal) / delta);
maxBucket[index] = Math.max(maxBucket[index], arr[i]);
minBucket[index] = Math.min(minBucket[index], arr[i]);
}
// Finding maximum difference between maximum value
// of previous bucket minus minimum of current bucket.
var prev_val = minVal;
var max_gap = 0;
for (var i = 0; i < n - 1; i++) {
if (minBucket[i] == 1000000000)
continue;
max_gap = Math.max(max_gap, minBucket[i] - prev_val);
prev_val = maxBucket[i];
}
max_gap = Math.max(max_gap, maxVal - prev_val);
return max_gap;
}
var arr = [1, 10, 5];
var n = arr.length;
document.write( maxSortedAdjacentDiff(arr, n));
</script>
5
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA