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