Dada una array arr[] de N enteros, la tarea es ordenar la array en orden no decreciente realizando el 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[] = {1, 2, 1, 4, 3}
Salida: 2
Sume 1 al tercer elemento (1) y reste 1
al cuarto elemento (4) para obtener {1, 2, 2, 3, 3}
Entrada: arr[] = {1, 2, 2, 100}
Salida: 0 La
array dada ya está ordenada.
Observación: dado que nos gustaría minimizar el número de operaciones necesarias para ordenar la array, debería cumplirse lo siguiente:
- Un número nunca se reducirá a un valor menor que el mínimo de la array inicial.
- Un número nunca se incrementará a un valor mayor que el máximo de la array inicial.
- El número de operaciones requeridas para cambiar un número de X a Y es abs(X – Y).
Enfoque: en base a la observación anterior, este problema se puede resolver mediante programación dinámica.
- Deje que DP(i, j) represente las operaciones mínimas necesarias para hacer que los primeros elementos i del arreglo se clasifiquen en orden no decreciente cuando el i – ésimo elemento es igual a j .
- Ahora es necesario calcular DP(N, j) para todos los valores posibles de j , donde N es el tamaño de la array. Según las observaciones, j ≥ el elemento más pequeño del arreglo inicial y j ≤ el elemento más grande del arreglo inicial .
- Los casos base en el DP(i, j) donde i = 1 se pueden responder fácilmente. ¿Cuáles son las operaciones mínimas necesarias para clasificar el primer elemento en orden no decreciente de modo que el primer elemento sea igual a j ? DP(1, j) = abs(arreglo[1] – j) .
- Ahora considere DP(i, j) para i > 1 . Si el i -ésimo elemento se establece en j , entonces los 1 er i – 1 elementos deben ordenarse y el (i – 1) ésimo elemento debe ser ≤ j , es decir , DP(i, j) = (mínimo de DP(i – 1 , k) donde k va de 1 a j ) + abs(array[i] – j)
- Usando la relación de recurrencia anterior y los casos base, el resultado se puede calcular fácilmente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum number
// of given operations required
// to sort the array
int getMinimumOps(vector<int> ar)
{
// Number of elements in the array
int n = ar.size();
// Smallest element in the array
int small = *min_element(ar.begin(), ar.end());
// Largest element in the array
int large = *max_element(ar.begin(), ar.end());
/*
dp(i, j) represents the minimum number
of operations needed to make the
array[0 .. i] sorted in non-decreasing
order given that ith element is j
*/
int dp[n][large + 1];
// Fill the dp[]][ array for base cases
for (int j = small; j <= large; j++) {
dp[0][j] = abs(ar[0] - j);
}
/*
Using results for the first (i - 1)
elements, calculate the result
for the ith element
*/
for (int i = 1; i < n; i++) {
int minimum = INT_MAX;
for (int j = small; j <= large; j++) {
/*
If the ith element is j then we can have
any value from small to j for the i-1 th
element
We choose the one that requires the
minimum operations
*/
minimum = min(minimum, dp[i - 1][j]);
dp[i][j] = minimum + abs(ar[i] - j);
}
}
/*
If we made the (n - 1)th element equal to j
we required dp(n-1, j) operations
We choose the minimum among all possible
dp(n-1, j) where j goes from small to large
*/
int ans = INT_MAX;
for (int j = small; j <= large; j++) {
ans = min(ans, dp[n - 1][j]);
}
return ans;
}
// Driver code
int main()
{
vector<int> ar = { 1, 2, 1, 4, 3 };
cout << getMinimumOps(ar);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the minimum number
// of given operations required
// to sort the array
static int getMinimumOps(Vector<Integer> ar)
{
// Number of elements in the array
int n = ar.size();
// Smallest element in the array
int small = Collections.min(ar);
// Largest element in the array
int large = Collections.max(ar);
/*
dp(i, j) represents the minimum number
of operations needed to make the
array[0 .. i] sorted in non-decreasing
order given that ith element is j
*/
int [][]dp = new int[n][large + 1];
// Fill the dp[]][ array for base cases
for (int j = small; j <= large; j++)
{
dp[0][j] = Math.abs(ar.get(0) - j);
}
/*
Using results for the first (i - 1)
elements, calculate the result
for the ith element
*/
for (int i = 1; i < n; i++)
{
int minimum = Integer.MAX_VALUE;
for (int j = small; j <= large; j++)
{
/*
If the ith element is j then we can have
any value from small to j for the i-1 th
element
We choose the one that requires the
minimum operations
*/
minimum = Math.min(minimum, dp[i - 1][j]);
dp[i][j] = minimum + Math.abs(ar.get(i) - j);
}
}
/*
If we made the (n - 1)th element equal to j
we required dp(n-1, j) operations
We choose the minimum among all possible
dp(n-1, j) where j goes from small to large
*/
int ans = Integer.MAX_VALUE;
for (int j = small; j <= large; j++)
{
ans = Math.min(ans, dp[n - 1][j]);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
Integer []arr = { 1, 2, 1, 4, 3 };
Vector<Integer> ar = new Vector<>(Arrays.asList(arr));
System.out.println(getMinimumOps(ar));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to return the minimum number # of given operations required # to sort the array def getMinimumOps(ar): # Number of elements in the array n = len(ar) # Smallest element in the array small = min(ar) # Largest element in the array large = max(ar) """ dp(i, j) represents the minimum number of operations needed to make the array[0 .. i] sorted in non-decreasing order given that ith element is j """ dp = [[ 0 for i in range(large + 1)] for i in range(n)] # Fill the dp[]][ array for base cases for j in range(small, large + 1): dp[0][j] = abs(ar[0] - j) """ /* Using results for the first (i - 1) elements, calculate the result for the ith element */ """ for i in range(1, n): minimum = 10**9 for j in range(small, large + 1): # """ # /* # If the ith element is j then we can have # any value from small to j for the i-1 th # element # We choose the one that requires the # minimum operations # """ minimum = min(minimum, dp[i - 1][j]) dp[i][j] = minimum + abs(ar[i] - j) """ /* If we made the (n - 1)th element equal to j we required dp(n-1, j) operations We choose the minimum among all possible dp(n-1, j) where j goes from small to large */ """ ans = 10**9 for j in range(small, large + 1): ans = min(ans, dp[n - 1][j]) return ans # Driver code ar = [1, 2, 1, 4, 3] print(getMinimumOps(ar)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
using System.Linq;
using System.Collections.Generic;
class GFG
{
// Function to return the minimum number
// of given operations required
// to sort the array
static int getMinimumOps(List<int> ar)
{
// Number of elements in the array
int n = ar.Count;
// Smallest element in the array
int small = ar.Min();
// Largest element in the array
int large = ar.Max();
/*
dp(i, j) represents the minimum number
of operations needed to make the
array[0 .. i] sorted in non-decreasing
order given that ith element is j
*/
int [,]dp = new int[n, large + 1];
// Fill the dp[], array for base cases
for (int j = small; j <= large; j++)
{
dp[0, j] = Math.Abs(ar[0] - j);
}
/*
Using results for the first (i - 1)
elements, calculate the result
for the ith element
*/
for (int i = 1; i < n; i++)
{
int minimum = int.MaxValue;
for (int j = small; j <= large; j++)
{
/*
If the ith element is j then we can have
any value from small to j for the i-1 th
element
We choose the one that requires the
minimum operations
*/
minimum = Math.Min(minimum, dp[i - 1, j]);
dp[i, j] = minimum + Math.Abs(ar[i] - j);
}
}
/*
If we made the (n - 1)th element equal to j
we required dp(n-1, j) operations
We choose the minimum among all possible
dp(n-1, j) where j goes from small to large
*/
int ans = int.MaxValue;
for (int j = small; j <= large; j++)
{
ans = Math.Min(ans, dp[n - 1, j]);
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 1, 4, 3 };
List<int> ar = new List<int>(arr);
Console.WriteLine(getMinimumOps(ar));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum number
// of given operations required
// to sort the array
function getMinimumOps(ar)
{
// Number of elements in the array
var n = ar.length;
// Smallest element in the array
var small = Math.min.apply(Math,ar);
// Largest element in the array
var large = Math.max.apply(Math,ar);
/*
dp(i, j) represents the minimum number
of operations needed to make the
array[0 .. i] sorted in non-decreasing
order given that ith element is j
*/
var dp = new Array(n);
var i,j;
for(i=0;i<dp.length;i++)
dp[i] = new Array(large+1);
// Fill the dp[]][ array for base cases
for (j = small; j <= large; j++) {
dp[0][j] = Math.abs(ar[0] - j);
}
/*
Using results for the first (i - 1)
elements, calculate the result
for the ith element
*/
for (i = 1; i < n; i++) {
var minimum = 2147483647;
for (j = small; j <= large; j++) {
/*
If the ith element is j then we can have
any value from small to j for the i-1 th
element
We choose the one that requires the
minimum operations
*/
minimum = Math.min(minimum, dp[i - 1][j]);
dp[i][j] = minimum + Math.abs(ar[i] - j);
}
}
/*
If we made the (n - 1)th element equal to j
we required dp(n-1, j) operations
We choose the minimum among all possible
dp(n-1, j) where j goes from small to large
*/
var ans = 2147483647;
for (j = small; j <= large; j++) {
ans = Math.min(ans, dp[n - 1][j]);
}
return ans;
}
// Driver code
var ar = [1, 2, 1, 4, 3];
document.write(getMinimumOps(ar));
</script>
Producción:
2
Análisis de
complejidad: Complejidad de tiempo: O(N*R), la complejidad de tiempo para el enfoque anterior es O(N * R) donde N es el número de elementos en la array y R = elemento más grande – más pequeño de la array + 1.
Auxiliar Espacio: O(N * grande)
Publicación traducida automáticamente
Artículo escrito por KartikArora y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA