Máxima diferencia adyacente en una array en su forma ordenada

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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *