Dada una array arr[] de tamaño N que tiene enteros distintos del 1 al N, la tarea es contar el número mínimo de pasos necesarios para clasificar la array en orden creciente eliminando cualquier elemento e insertándolo en la parte delantera o trasera de la array . .
Ejemplos:
Entrada: arr[ ] = {4, 1, 3, 2}
Salida: 2
Explicación:
La array dada se puede ordenar en orden creciente siguiendo dos operaciones:
Operación 1: Eliminar 3 y agregarlo al final de la array. {4, 1, 3 , 2} -> {4, 1, 2, 3 }
Operación 2: elimine 4 y agréguelo al final de la array. { 4 , 1, 2, 3} -> {1, 2, 3, 4 }Entrada: arr[ ] = {4, 1, 2, 5, 3}
Salida: 2
Enfoque: el problema se puede resolver utilizando el hecho de que para ordenar la array en un número mínimo de pasos, se debe mover el número mínimo de elementos hacia adelante o hacia atrás . Además, los elementos cuya posición se debe cambiar no estarán inicialmente en orden creciente . Entonces, el problema se reduce a encontrar el subarreglo creciente más largo , ya que solo esos elementos del arreglo no se moverán.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach #include<bits/stdc++.h> using namespace std; // Function to find the minimum steps // to sort the array void findMinStepstoSort(int arr[], int N){ // Storing the positions of elements map<int,int> pos; for(int i = 0; i < N; i++) pos[arr[i]] = i; // Initialize answer int ans = N-1; int prev = -1; int count = 0; // Traversing the array for(int i = 1; i < N + 1; i++){ // If current is greater than // previous if(pos[i] > prev) count += 1; // else if current is less than // previous else count = 1; // Updating previous prev = pos[i]; // Updating ans ans = min(ans, N - count); } cout<<ans; } // Driver Code int main(){ int N = 5; int arr[] = {4, 1, 2, 5, 3}; findMinStepstoSort(arr, N); } // This code is contributed by SURENDRA_GANGWAR.
Java
// JAVA program for the above approach import java.util.*; class GFG{ // Function to find the minimum steps // to sort the array static void findMinStepstoSort(int arr[], int N){ // Storing the positions of elements HashMap<Integer,Integer> pos = new HashMap<>(); for(int i = 0; i < N; i++) pos.put(arr[i], i); // Initialize answer int ans = N - 1; int prev = -1; int count = 0; // Traversing the array for(int i = 1; i < N + 1; i++){ // If current is greater than // previous if(pos.get(i) > prev) count += 1; // else if current is less than // previous else count = 1; // Updating previous prev = pos.get(i); // Updating ans ans = Math.min(ans, N - count); } System.out.print(ans); } // Driver Code public static void main(String[] args){ int N = 5; int arr[] = {4, 1, 2, 5, 3}; findMinStepstoSort(arr, N); } } // This code is contributed by gauravrajput1
Python3
# Python program for the above approach # Function to find the minimum steps # to sort the array def findMinStepstoSort(arr, N): # Storing the positions of elements pos = {arr[i]:i for i in range(N)} # Initialize answer ans = N-1 prev = -1;count = 0 # Traversing the array for i in range(1, N + 1): # If current is greater than # previous if pos[i] > prev: count += 1 # else if current is less than # previous else: count = 1 # Updating previous prev = pos[i] # Updating ans ans = min(ans, N - count) print(ans) # Driver Code if __name__ == '__main__': N = 5 arr = [4, 1, 2, 5, 3] findMinStepstoSort(arr, N)
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the minimum steps // to sort the array static void findMinStepstoSort(int[] arr, int N){ // Storing the positions of elements Dictionary<int, int> pos = new Dictionary<int, int>(); for(int i = 0; i < N; i++) pos[arr[i]] = i; // Initialize answer int ans = N - 1; int prev = -1; int count = 0; // Traversing the array for(int i = 1; i < N + 1; i++){ // If current is greater than // previous if(pos[i] > prev) count += 1; // else if current is less than // previous else count = 1; // Updating previous prev = pos[i]; // Updating ans ans = Math.Min(ans, N - count); } Console.WriteLine(ans); } // Driver Code public static void Main (string[] args) { int N = 5; int[] arr = {4, 1, 2, 5, 3}; findMinStepstoSort(arr, N); } } // This code is contributed by sanjoy_62.
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum steps // to sort the array function findMinStepstoSort(arr, N) { // Storing the positions of elements let pos = new Array(N); for (let i = 0; i < N; i++) { pos[i] = arr[i]; } // Initialize answer ans = N - 1 prev = -1; count = 0 // Traversing the array for (let i = 1; i < N + 1; i++) { // If current is greater than // previous if (pos[i] > prev) count += 1 // else if current is less than // previous else count = 1 // Updating previous prev = pos[i] // Updating ans ans = Math.min(ans, N - count) } document.write(ans) } let N = 5 let arr = [4, 1, 2, 5, 3] findMinStepstoSort(arr, N) // This code is contributed by Potta Lokesh </script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)