Incremento o decremento mínimo requerido para ordenar la array | Enfoque de arriba hacia abajo

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros, la tarea es clasificar la array en orden creciente realizando un número mínimo de operaciones. En una sola operación, un elemento de la array puede incrementarse o disminuirse en 1. Imprime el número mínimo de operaciones requeridas.
Ejemplos:

Entrada: arr[] = {5, 4, 3, 2, 1} 
Salida: 6 
Explicación: 
La array ordenada de arr[] es {3, 3, 3, 3, 3} 
Por lo tanto, los incrementos/decrementos mínimos son: 
En índice 0, 5 – 3 = 2 (decremento 2) 
En índice 1, 4 – 3 = 1 (decremento 1) 
En índice 3, 2 + 1 = 3 (incremento 1) 
En índice 4, 1 + 2 = 3 (incremento 2 ) 
El incremento/decremento total es 2 + 1 + 1 + 2 = 6.
Entrada: arr[] = {1, 2, 3, 4} 
Salida: 0 
Explicación: 
La array ya está ordenada.

Enfoque de abajo hacia arriba: este problema se puede resolver utilizando la programación dinámica . En este artículo se analiza un enfoque de abajo hacia arriba para esta declaración del problema . Enfoque de arriba hacia abajo: aquí usaremos la programación dinámica de arriba hacia abajo para resolver este problema. Deje que la array 2D (digamos dp[i][j]) se use para almacenar el índice i donde el último elemento está en el índice j . A continuación se muestran los pasos: 

 

  1. Para ordenar el elemento de la array usando las operaciones dadas, sabemos que un elemento no puede volverse mayor que el valor máximo de la array y menor que el valor mínimo de la array (digamos m ) por incremento o decremento.
  2. Por lo tanto, fije un elemento (digamos X ) en la i-ésima posición, luego (i-1) el valor de la posición (digamos Y ) puede estar en el rango [m, X] .
  3. Siga colocando el elemento más pequeño menor o igual a arr[i] en la posición (i-1) para cada índice i de arr[] y calcule el incremento o decremento mínimo sumando abs(arr[i] – Y) .
  4. Por lo tanto, la relación de recurrencia para el enfoque mencionado anteriormente se puede escribir como:
     

 
 

dp[i][j] = min(dp[i][j], abs(arr[i] – Y) + función_recursiva(i-1, Y)) donde m ≤ Y ≤ arr[j] 
.

 

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Dp array to memoized
// the value recursive call
int dp[1000][1000];
 
// Function to find the minimum increment
// or decrement needed to make the array
// sorted
int minimumIncDec(int arr[], int N,
                  int maxE, int minE)
{
    // If only one element is present,
    // then arr[] is sorted
    if (N == 0) {
        return 0;
    }
 
    // If dp[N][maxE] is precalculated,
    // then return the result
    if (dp[N][maxE])
        return dp[N][maxE];
 
    int ans = INT_MAX;
 
    // Iterate from minE to maxE which
    // placed at previous index
    for (int k = minE; k <= maxE; k++) {
 
        // Update the answer according to
        // recurrence relation
        int x = minimumIncDec(arr, N - 1, k, minE);
        ans = min(ans,x + abs(arr[N - 1] - k));
    }
 
    // Memoized the value
    // for dp[N][maxE]
    dp[N][maxE] = ans;
 
    // Return the final result
    return dp[N][maxE];
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 4, 3, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Find the minimum and maximum
    // element from the arr[]
    int minE = *min_element(arr, arr + N);
    int maxE = *max_element(arr, arr + N);
 
    // Function Call
    cout << minimumIncDec(
        arr, N, maxE, minE);
    return 0;
}

Java

// Java program of the above approach
import java.util.*;
 
class GFG{
 
// Dp array to memoized
// the value recursive call
static int [][]dp = new int[1000][1000];
 
// Function to find the minimum increment
// or decrement needed to make the array
// sorted
static int minimumIncDec(int arr[], int N,
                         int maxE, int minE)
{
     
    // If only one element is present,
    // then arr[] is sorted
    if (N == 0)
    {
        return 0;
    }
     
    // If dp[N][maxE] is precalculated,
    // then return the result
    if (dp[N][maxE] != 0)
        return dp[N][maxE];
 
    int ans = Integer.MAX_VALUE;
 
    // Iterate from minE to maxE which
    // placed at previous index
    for(int k = minE; k <= maxE; k++)
    {
 
        // Update the answer according to
        // recurrence relation
        int x = minimumIncDec(arr, N - 1, k, minE);
        ans = Math.min(ans,
                       x + Math.abs(arr[N - 1] - k));
    }
 
    // Memoized the value
    // for dp[N][maxE]
    dp[N][maxE] = ans;
 
    // Return the final result
    return dp[N][maxE];
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 5, 4, 3, 2, 1 };
    int N = arr.length;
 
    // Find the minimum and maximum
    // element from the arr[]
    int minE = Arrays.stream(arr).min().getAsInt();
    int maxE = Arrays.stream(arr).max().getAsInt();
 
    // Function call
    System.out.print(minimumIncDec(
        arr, N, maxE, minE));
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 program of the above approach
import sys
 
# Dp array to memoized
# the value recursive call
dp = [[ 0 for x in range(1000)]
          for y in range(1000)]
 
# Function to find the minimum increment
# or decrement needed to make the array
# sorted
def minimumIncDec(arr, N, maxE, minE):
 
    # If only one element is present,
    # then arr[] is sorted
    if (N == 0):
        return 0
 
    # If dp[N][maxE] is precalculated,
    # then return the result
    if (dp[N][maxE]):
        return dp[N][maxE]
 
    ans = sys.maxsize
 
    # Iterate from minE to maxE which
    # placed at previous index
    for k in range(minE, maxE + 1):
 
        # Update the answer according to
        # recurrence relation
        x = minimumIncDec(arr, N - 1, k, minE)
        ans = min(ans, x + abs(arr[N - 1] - k))
 
    # Memoized the value
    # for dp[N][maxE]
    dp[N][maxE] = ans
 
    # Return the final result
    return dp[N][maxE]
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 5, 4, 3, 2, 1 ]
    N = len(arr)
 
    # Find the minimum and maximum
    # element from the arr[]
    minE = min(arr)
    maxE = max(arr)
 
    # Function Call
    print(minimumIncDec(arr, N, maxE, minE))
 
# This code is contributed by chitranayal

C#

// C# program of the above approach
using System;
using System.Linq;
 
class GFG{
 
// Dp array to memoized
// the value recursive call
static int [,]dp = new int[1000, 1000];
 
// Function to find the minimum increment
// or decrement needed to make the array
// sorted
static int minimumIncDec(int []arr, int N,
                         int maxE, int minE)
{
     
    // If only one element is present,
    // then []arr is sorted
    if (N == 0)
    {
        return 0;
    }
     
    // If dp[N,maxE] is precalculated,
    // then return the result
    if (dp[N, maxE] != 0)
        return dp[N, maxE];
 
    int ans = int.MaxValue;
 
    // Iterate from minE to maxE which
    // placed at previous index
    for(int k = minE; k <= maxE; k++)
    {
 
        // Update the answer according to
        // recurrence relation
        int x = minimumIncDec(arr, N - 1, k, minE);
        ans = Math.Min(ans,
                       x + Math.Abs(arr[N - 1] - k));
    }
 
    // Memoized the value
    // for dp[N,maxE]
    dp[N, maxE] = ans;
 
    // Return the readonly result
    return dp[N,maxE];
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 5, 4, 3, 2, 1 };
    int N = arr.Length;
 
    // Find the minimum and maximum
    // element from the []arr
    int minE = arr.Min();
    int maxE = arr.Max();
 
    // Function call
    Console.Write(minimumIncDec(arr, N,
                                maxE, minE));
}
}
 
// This code is contributed by Rohit_ranjan

Javascript

<script>
 
// JavaScript program of the above approach
 
// Dp array to memoized
// the value recursive call
let dp = new Array();
 
for(let i = 0; i < 1000; i++){
    let temp = [];
    for(let j = 0; j < 1000; j++){
        temp.push([])
    }
    dp.push(temp)
}
 
// Function to find the minimum increment
// or decrement needed to make the array
// sorted
 
function minimumIncDec(arr, N, maxE, minE)
{
    // If only one element is present,
    // then arr[] is sorted
    if (N == 0) {
        return 0;
    }
    // If dp[N][maxE] is precalculated,
    // then return the result
    if (!dp[N][maxE])
        return dp[N][maxE];
 
    let ans = Number.MAX_SAFE_INTEGER;
 
    // Iterate from minE to maxE which
    // placed at previous index
    for (let k = minE; k <= maxE; k++) {
 
        // Update the answer according to
        // recurrence relation
        let x = minimumIncDec(arr, N - 1, k, minE);
        ans = Math.min(ans,x + Math.abs(arr[N - 1] - k));
    }
 
    // Memoized the value
    // for dp[N][maxE]
    dp[N][maxE] = ans;
 
    // Return the final result
    return dp[N][maxE];
}
 
// Driver Code
 
    let arr = [ 5, 4, 3, 2, 1 ];
    let N = arr.length;
 
    // Find the minimum and maximum
    // element from the arr[]
    let minE = arr.sort((a, b) => a - b)[0];
    let maxE = arr.sort((a, b) => b - a)[0];
 
    // Function Call
    document.write(minimumIncDec(arr, N, maxE, minE));
 
// This code is contributed by _saurabh_jaiswal
 
</script>
Producción: 

6

 

Complejidad de Tiempo: O(N*maxE) 
Espacio Auxiliar: O(N 2 )
 

Publicación traducida automáticamente

Artículo escrito por VikasVishwakarma1 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 *