Dada una array arr[] de tamaño N , la tarea es encontrar los movimientos mínimos al principio o al final de la array necesarios para ordenar la array en orden no decreciente .
Ejemplos:
Entrada: arr[] = {4, 7, 2, 3, 9}
Salida: 2
Explicación:
Realice las siguientes operaciones:
Paso 1: Mueva el elemento 3 al inicio de la array. Ahora, arr[] se modifica a {3, 4, 7, 2, 9}.
Paso 2: Mueva el elemento 2 al comienzo de la array. Ahora, arr[] se modifica a {2, 3, 4, 7, 9}.
Ahora, la array resultante está ordenada.
Por lo tanto, los movimientos mínimos requeridos son 2.Entrada: arr[] = {1, 4, 5, 7, 12}
Salida: 0
Explicación:
La array ya está ordenada. Por lo tanto, no se requieren movimientos.
Enfoque ingenuo: el enfoque más simple es verificar para cada elemento de la array, cuántos movimientos se requieren para ordenar la array dada arr[] . Para cada elemento de la array, si no está en su posición ordenada, surgen las siguientes posibilidades:
- Mueva el elemento actual al frente.
- De lo contrario, mueva el elemento actual al final.
Después de realizar las operaciones anteriores, imprima el número mínimo de operaciones requeridas para ordenar la array. A continuación se muestra la relación de recurrencia de la misma:
- Si la array arr[] es igual a la array brr[] , entonces devuelve 0 .
- Si arr[i] < brr[j] , entonces el recuento de operaciones será:
1 + función_recursiva(arr, brr, i + 1, j + 1)
- De lo contrario, el recuento de operaciones se puede calcular tomando el máximo de los siguientes estados:
- función_recursiva(arr, brr, i + 1, j)
- función_recursiva(arr, brr, i, j + 1)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the minimum
// moves required to convert arr[] to brr[]
int minOperations(int arr1[], int arr2[],
int i, int j,
int n)
{
// Base Case
int f = 0;
for (int i = 0; i < n; i++)
{
if (arr1[i] != arr2[i])
f = 1;
break;
}
if (f == 0)
return 0;
if (i >= n || j >= n)
return 0;
// If arr[i] < arr[j]
if (arr1[i] < arr2[j])
// Include the current element
return 1 + minOperations(arr1, arr2,
i + 1, j + 1, n);
// Otherwise, excluding the current element
return max(minOperations(arr1, arr2,
i, j + 1, n),
minOperations(arr1, arr2,
i + 1, j, n));
}
// Function that counts the minimum
// moves required to sort the array
void minOperationsUtil(int arr[], int n)
{
int brr[n];
for (int i = 0; i < n; i++)
brr[i] = arr[i];
sort(brr, brr + n);
int f = 0;
// If both the arrays are equal
for (int i = 0; i < n; i++)
{
if (arr[i] != brr[i])
// No moves required
f = 1;
break;
}
// Otherwise
if (f == 1)
// Print minimum
// operations required
cout << (minOperations(arr, brr,
0, 0, n));
else
cout << "0";
}
// Driver code
int main()
{
int arr[] = {4, 7, 2, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
minOperationsUtil(arr, n);
}
// This code is contributed by Chitranayal
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
import java.lang.Math;
class GFG{
// Function that counts the minimum
// moves required to convert arr[] to brr[]
static int minOperations(int arr1[], int arr2[],
int i, int j)
{
// Base Case
if (arr1.equals(arr2))
return 0;
if (i >= arr1.length || j >= arr2.length)
return 0;
// If arr[i] < arr[j]
if (arr1[i] < arr2[j])
// Include the current element
return 1 + minOperations(arr1, arr2,
i + 1, j + 1);
// Otherwise, excluding the current element
return Math.max(minOperations(arr1, arr2,
i, j + 1),
minOperations(arr1, arr2,
i + 1, j));
}
// Function that counts the minimum
// moves required to sort the array
static void minOperationsUtil(int[] arr)
{
int brr[] = new int[arr.length];
for(int i = 0; i < arr.length; i++)
brr[i] = arr[i];
Arrays.sort(brr);
// If both the arrays are equal
if (arr.equals(brr))
// No moves required
System.out.print("0");
// Otherwise
else
// Print minimum operations required
System.out.println(minOperations(arr, brr,
0, 0));
}
// Driver code
public static void main(final String[] args)
{
int arr[] = { 4, 7, 2, 3, 9 };
minOperationsUtil(arr);
}
}
// This code is contributed by bikram2001jha
Python3
# Python3 program for the above approach
# Function that counts the minimum
# moves required to convert arr[] to brr[]
def minOperations(arr1, arr2, i, j):
# Base Case
if arr1 == arr2:
return 0
if i >= len(arr1) or j >= len(arr2):
return 0
# If arr[i] < arr[j]
if arr1[i] < arr2[j]:
# Include the current element
return 1 \
+ minOperations(arr1, arr2, i + 1, j + 1)
# Otherwise, excluding the current element
return max(minOperations(arr1, arr2, i, j + 1),
minOperations(arr1, arr2, i + 1, j))
# Function that counts the minimum
# moves required to sort the array
def minOperationsUtil(arr):
brr = sorted(arr);
# If both the arrays are equal
if(arr == brr):
# No moves required
print("0")
# Otherwise
else:
# Print minimum operations required
print(minOperations(arr, brr, 0, 0))
# Driver Code
arr = [4, 7, 2, 3, 9]
minOperationsUtil(arr)
C#
// C# program for the above approach
using System;
class GFG{
// Function that counts the minimum
// moves required to convert arr[] to brr[]
static int minOperations(int[] arr1, int[] arr2,
int i, int j)
{
// Base Case
if (arr1.Equals(arr2))
return 0;
if (i >= arr1.Length ||
j >= arr2.Length)
return 0;
// If arr[i] < arr[j]
if (arr1[i] < arr2[j])
// Include the current element
return 1 + minOperations(arr1, arr2,
i + 1, j + 1);
// Otherwise, excluding the current element
return Math.Max(minOperations(arr1, arr2,
i, j + 1),
minOperations(arr1, arr2,
i + 1, j));
}
// Function that counts the minimum
// moves required to sort the array
static void minOperationsUtil(int[] arr)
{
int[] brr = new int[arr.Length];
for(int i = 0; i < arr.Length; i++)
brr[i] = arr[i];
Array.Sort(brr);
// If both the arrays are equal
if (arr.Equals(brr))
// No moves required
Console.Write("0");
// Otherwise
else
// Print minimum operations required
Console.WriteLine(minOperations(arr, brr,
0, 0));
}
// Driver code
static void Main()
{
int[] arr = { 4, 7, 2, 3, 9 };
minOperationsUtil(arr);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function that counts the minimum
// moves required to convert arr[] to brr[]
function minOperations(arr1, arr2,
i, j, n)
{
// Base Case
let f = 0;
for(let i = 0; i < n; i++)
{
if (arr1[i] != arr2[i])
f = 1;
break;
}
if (f == 0)
return 0;
if (i >= n || j >= n)
return 0;
// If arr[i] < arr[j]
if (arr1[i] < arr2[j])
// Include the current element
return 1 + minOperations(arr1, arr2,
i + 1, j + 1, n);
// Otherwise, excluding the current element
return Math.max(minOperations(arr1, arr2,
i, j + 1, n),
minOperations(arr1, arr2,
i + 1, j, n));
}
// Function that counts the minimum
// moves required to sort the array
function minOperationsUtil(arr, n)
{
let brr = new Array(n);
for(let i = 0; i < n; i++)
brr[i] = arr[i];
brr.sort();
let f = 0;
// If both the arrays are equal
for(let i = 0; i < n; i++)
{
if (arr[i] != brr[i])
// No moves required
f = 1;
break;
}
// Otherwise
if (f == 1)
// Print minimum
// operations required
document.write(minOperations(arr, brr,
0, 0, n));
else
cout << "0";
}
// Driver code
let arr = [ 4, 7, 2, 3, 9 ];
let n = arr.length;
minOperationsUtil(arr, n);
// This code is contributed by Mayank Tyagi
</script>
Producción
2
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior tiene muchos subproblemas superpuestos . Por lo tanto, el enfoque anterior se puede optimizar mediante la programación dinámica . Siga los pasos a continuación para resolver el problema:
- Mantenga una tabla de array 2D [][] para almacenar los resultados calculados.
- Aplicar la recursividad para resolver el problema usando los resultados de subproblemas más pequeños.
- Si arr1[i] < arr2[j] , entonces devuelve 1 + minOperations(arr1, arr2, i + 1, j – 1, table)
- De lo contrario, mueva el i-ésimo elemento de la array al final o el j-ésimo elemento de la array al frente. Por lo tanto, la relación de recurrencia es:
tabla[i][j] = max(minOperations(arr1, arr2, i, j + 1, table), minOperations(arr1, arr2, i + 1, j, table))
- Finalmente, imprima el valor almacenado en table[0][N – 1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the minimum
// moves required to convert arr[] to brr[]
int minOperations(int arr1[], int arr2[],
int i, int j,
int n)
{
// Base Case
int f = 0;
for (int i = 0; i < n; i++)
{
if (arr1[i] != arr2[i])
f = 1;
break;
}
if (f == 0)
return 0;
if (i >= n || j >= n)
return 0;
// If arr[i] < arr[j]
if (arr1[i] < arr2[j])
// Include the current element
return 1 + minOperations(arr1, arr2,
i + 1, j + 1, n);
// Otherwise, excluding the current element
return max(minOperations(arr1, arr2,
i, j + 1, n),
minOperations(arr1, arr2,
i + 1, j, n));
}
// Function that counts the minimum
// moves required to sort the array
void minOperationsUtil(int arr[], int n)
{
int brr[n];
for (int i = 0; i < n; i++)
brr[i] = arr[i];
sort(brr, brr + n);
int f = 0;
// If both the arrays are equal
for (int i = 0; i < n; i++)
{
if (arr[i] != brr[i])
// No moves required
f = 1;
break;
}
// Otherwise
if (f == 1)
// Print minimum
// operations required
cout << (minOperations(arr, brr,
0, 0, n));
else
cout << "0";
}
// Driver code
int main()
{
int arr[] = {4, 7, 2, 3, 9};
int n = sizeof(arr) / sizeof(arr[0]);
minOperationsUtil(arr, n);
}
// This code is contributed by Chitranayal
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
import java.lang.Math;
class GFG{
// Function that counts the minimum
// moves required to convert arr[] to brr[]
static int minOperations(int arr1[], int arr2[],
int i, int j)
{
// Base Case
if (arr1.equals(arr2))
return 0;
if (i >= arr1.length || j >= arr2.length)
return 0;
// If arr[i] < arr[j]
if (arr1[i] < arr2[j])
// Include the current element
return 1 + minOperations(arr1, arr2,
i + 1, j + 1);
// Otherwise, excluding the current element
return Math.max(minOperations(arr1, arr2,
i, j + 1),
minOperations(arr1, arr2,
i + 1, j));
}
// Function that counts the minimum
// moves required to sort the array
static void minOperationsUtil(int[] arr)
{
int brr[] = new int[arr.length];
for(int i = 0; i < arr.length; i++)
brr[i] = arr[i];
Arrays.sort(brr);
// If both the arrays are equal
if (arr.equals(brr))
// No moves required
System.out.print("0");
// Otherwise
else
// Print minimum operations required
System.out.println(minOperations(arr, brr,
0, 0));
}
// Driver code
public static void main(final String[] args)
{
int arr[] = { 4, 7, 2, 3, 9 };
minOperationsUtil(arr);
}
}
// This code is contributed by bikram2001jha
Python3
# Python3 program for the above approach
# Function that counts the minimum
# moves required to convert arr[] to brr[]
def minOperations(arr1, arr2, i, j):
# Base Case
if arr1 == arr2:
return 0
if i >= len(arr1) or j >= len(arr2):
return 0
# If arr[i] < arr[j]
if arr1[i] < arr2[j]:
# Include the current element
return 1 \
+ minOperations(arr1, arr2, i + 1, j + 1)
# Otherwise, excluding the current element
return max(minOperations(arr1, arr2, i, j + 1),
minOperations(arr1, arr2, i + 1, j))
# Function that counts the minimum
# moves required to sort the array
def minOperationsUtil(arr):
brr = sorted(arr);
# If both the arrays are equal
if(arr == brr):
# No moves required
print("0")
# Otherwise
else:
# Print minimum operations required
print(minOperations(arr, brr, 0, 0))
# Driver Code
arr = [4, 7, 2, 3, 9]
minOperationsUtil(arr)
C#
// C# program for the above approach
using System;
class GFG{
// Function that counts the minimum
// moves required to convert arr[] to brr[]
static int minOperations(int[] arr1, int[] arr2,
int i, int j)
{
// Base Case
if (arr1.Equals(arr2))
return 0;
if (i >= arr1.Length ||
j >= arr2.Length)
return 0;
// If arr[i] < arr[j]
if (arr1[i] < arr2[j])
// Include the current element
return 1 + minOperations(arr1, arr2,
i + 1, j + 1);
// Otherwise, excluding the current element
return Math.Max(minOperations(arr1, arr2,
i, j + 1),
minOperations(arr1, arr2,
i + 1, j));
}
// Function that counts the minimum
// moves required to sort the array
static void minOperationsUtil(int[] arr)
{
int[] brr = new int[arr.Length];
for(int i = 0; i < arr.Length; i++)
brr[i] = arr[i];
Array.Sort(brr);
// If both the arrays are equal
if (arr.Equals(brr))
// No moves required
Console.Write("0");
// Otherwise
else
// Print minimum operations required
Console.WriteLine(minOperations(arr, brr,
0, 0));
}
// Driver code
static void Main()
{
int[] arr = { 4, 7, 2, 3, 9 };
minOperationsUtil(arr);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function that counts the minimum
// moves required to convert arr[] to brr[]
function minOperations(arr1, arr2,
i, j, n)
{
// Base Case
let f = 0;
for(let i = 0; i < n; i++)
{
if (arr1[i] != arr2[i])
f = 1;
break;
}
if (f == 0)
return 0;
if (i >= n || j >= n)
return 0;
// If arr[i] < arr[j]
if (arr1[i] < arr2[j])
// Include the current element
return 1 + minOperations(arr1, arr2,
i + 1, j + 1, n);
// Otherwise, excluding the current element
return Math.max(minOperations(arr1, arr2,
i, j + 1, n),
minOperations(arr1, arr2,
i + 1, j, n));
}
// Function that counts the minimum
// moves required to sort the array
function minOperationsUtil(arr, n)
{
let brr = new Array(n);
for(let i = 0; i < n; i++)
brr[i] = arr[i];
brr.sort();
let f = 0;
// If both the arrays are equal
for(let i = 0; i < n; i++)
{
if (arr[i] != brr[i])
// No moves required
f = 1;
break;
}
// Otherwise
if (f == 1)
// Print minimum
// operations required
document.write(minOperations(arr, brr,
0, 0, n));
else
cout << "0";
}
// Driver code
let arr = [ 4, 7, 2, 3, 9 ];
let n = arr.length;
minOperationsUtil(arr, n);
// This code is contributed by Mayank Tyagi
</script>
Producción
2
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(N 2 )
Estamos utilizando dos variables, a saber, i y j, para determinar un estado único de la etapa DP (Programación dinámica), y cada uno de i y j puede alcanzar N valores de 0 a N-1. Por lo tanto, la recursividad tendrá N*N número de transiciones cada una de costo O(1). Por lo tanto, la complejidad del tiempo es O(N*N).
Enfoque más eficiente: ordene la array dada manteniendo el índice de elementos a un lado, ahora encuentre la racha más larga de valores crecientes de índice. Esta racha más larga refleja que estos elementos ya están ordenados y realizan la operación anterior en el resto de los elementos. Tomemos la array anterior como ejemplo, arr = [8, 2, 1, 5, 4] después de ordenar sus valores de índice serán – [2, 1, 4, 3, 0], aquí la racha más larga es 2 (1, 4 ) lo que significa que, excepto estos 2 números, tenemos que seguir la operación anterior y ordenar la array, por lo tanto, 5 (arr.length) – 2 = 3 será la respuesta.
Implementación del enfoque anterior:
C++
// C++ algorithm of above approach
#include <bits/stdc++.h>
#include <vector>
using namespace std;
// Function to find minimum number of operation required
// so that array becomes meaningful
int minOperations(int arr[], int n)
{
// Initializing vector of pair type which contains value
// and index of arr
vector<pair<int, int>> vect;
for (int i = 0; i < n; i++) {
vect.push_back(make_pair(arr[i], i));
}
// Sorting array num on the basis of value
sort(vect.begin(), vect.end());
// Initializing variables used to find maximum
// length of increasing streak in index
int res = 1;
int streak = 1;
int prev = vect[0].second;
for (int i = 1; i < n; i++) {
if (prev < vect[i].second) {
res++;
// Updating streak
streak = max(streak, res);
}
else
res = 1;
prev = vect[i].second;
}
// Returning number of elements left except streak
return n - streak;
}
// Driver Code
int main()
{
int arr[] = { 4, 7, 2, 3, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int count = minOperations(arr, n);
cout << count;
}
Java
// Java algorithm for above approach
import java.util.*;
class GFG {
// Pair class which will store element of array with its
// index
public static class Pair {
int val;
int idx;
Pair(int val, int idx)
{
this.val = val;
this.idx = idx;
}
}
// Driver code
public static void main(String[] args)
{
int n = 5;
int[] arr = { 4, 7, 2, 3, 9 };
System.out.println(minOperations(arr, n));
}
// Function to find minimum number of operation required
// so that array becomes meaningful
public static int minOperations(int[] arr, int n)
{
// Initializing array of Pair type which can be used
// to sort arr with respect to its values
Pair[] num = new Pair[n];
for (int i = 0; i < n; i++) {
num[i] = new Pair(arr[i], i);
}
// Sorting array num on the basis of value
Arrays.sort(num, (Pair a, Pair b) -> a.val - b.val);
// Initializing variables used to find maximum
// length of increasing streak in index
int res = 1;
int streak = 1;
int prev = num[0].idx;
for (int i = 1; i < n; i++) {
if (prev < num[i].idx) {
res++;
// Updating streak
streak = Math.max(res, streak);
}
else
res = 1;
prev = num[i].idx;
}
// Returning number of elements left except streak
return n - streak;
}
}
Python3
# Python algorithm of above approach # Function to find minimum number of operation required # so that array becomes meaningful def minOperations(arr, n): # Initializing vector of pair type which contains value # and index of arr vect = [] for i in range(n): vect.append([arr[i], i]) # Sorting array num on the basis of value vect.sort() # Initializing variables used to find maximum # length of increasing streak in index res = 1 streak = 1 prev = vect[0][1] for i in range(1,n): if (prev < vect[i][1]): res += 1 # Updating streak streak = max(streak, res) else: res = 1 prev = vect[i][1] # Returning number of elements left except streak return n - streak # Driver code arr = [ 4, 7, 2, 3, 9 ] n = len(arr) count = minOperations(arr, n) print(count) # This code is contributed by shinjanpatra.
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Pair class which will store element of array with its
// index
class Pair {
public int val;
public int idx;
public Pair(int val, int idx)
{
this.val = val;
this.idx = idx;
}
}
// Comparator Function
class Comp : IComparer<Pair>{
public int Compare(Pair a, Pair b)
{
return a.val - b.val;
}
}
// Function to find minimum number of operation required
// so that array becomes meaningful
public static int minOperations(int[] arr, int n)
{
// Initializing array of Pair type which can be used
// to sort arr with respect to its values
Pair[] num = new Pair[n];
for (int i = 0 ; i < n ; i++) {
num[i] = new Pair(arr[i], i);
}
// Sorting array num on the basis of value
Array.Sort(num, new Comp());
// Initializing variables used to find maximum
// length of increasing streak in index
int res = 1;
int streak = 1;
int prev = num[0].idx;
for (int i = 1 ; i < n ; i++) {
if (prev < num[i].idx) {
res++;
// Updating streak
streak = Math.Max(res, streak);
}
else{
res = 1;
}
prev = num[i].idx;
}
// Returning number of elements left except streak
return n - streak;
}
// Driver code
public static void Main(string[] args){
int n = 5;
int[] arr = new int[]{ 4, 7, 2, 3, 9 };
Console.WriteLine(minOperations(arr, n));
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// JavaScript algorithm of above approach
// Function to find minimum number of operation required
// so that array becomes meaningful
function minOperations(arr, n)
{
// Initializing vector of pair type which contains value
// and index of arr
let vect = [];
for (let i = 0; i < n; i++) {
vect.push([arr[i], i]);
}
// Sorting array num on the basis of value
vect.sort();
// Initializing variables used to find maximum
// length of increasing streak in index
let res = 1;
let streak = 1;
let prev = vect[0][1];
for (let i = 1; i < n; i++) {
if (prev < vect[i][1]) {
res++;
// Updating streak
streak = Math.max(streak, res);
}
else
res = 1;
prev = vect[i][1];
}
// Returning number of elements left except streak
return n - streak;
}
// driver ocde
let arr = [ 4, 7, 2, 3, 9 ];
let n = arr.length;
let count = minOperations(arr, n);
document.write(count,"</br>");
// This code is contributed by shinjanpatra.
</script>
Producción
2
Complejidad de tiempo: O(nlogn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA