Dada una array arr[] de tamaño N que es una permutación de 1 a N , la tarea es encontrar la permutación lexicográficamente más pequeña que se puede formar invirtiendo como máximo un subarreglo.
Ejemplos:
Entrada: arr[] = {1, 3, 4, 2, 5}
Salida: 1 2 4 3 5
Explicación: El subarreglo del índice 1 al índice 3 se puede invertir para obtener la permutación lexicográficamente más pequeña.Entrada: arr[] = {4, 3, 1, 2}
Salida: 1 3 4 2
Enfoque: La idea para resolver el problema se basa en el recorrido de la array .
- En el problema dado, la permutación lexicográficamente más pequeña se puede obtener colocando el menor número en su lugar correcto mediante una inversión recorriendo desde la izquierda y comprobando que (i+1) es igual a arr[i]
- Si no es igual, busque el índice de ese i+1 en el arreglo e invierta el subarreglo desde el i-ésimo índice hasta la posición (i+1) .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the // Lexicographically smallest // Permutation by one subarray reversal void lexsmallest(vector<int>& arr, int n) { // Initialize the variables // To store the first and last // Position of the subarray int first = -1, flag = 0, find = -1, last = -1; // Traverse the array // And check if arr[i]!=i+1 for (int i = 0; i < n; i++) { if (arr[i] != i + 1) { flag = 1; // Mark the first position // Of the Subarray to be reversed first = i; find = i + 1; break; } } // If flag == 0, it is the // Smallest permutation, // So print the array if (flag == 0) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } // Check where the minimum element is present else { for (int i = 0; i < n; i++) { // It is the last position // Of the subarray to be // Reversed if (arr[i] == find) { last = i; break; } } // Reverse the subarray // And print the array reverse(arr.begin() + first, arr.begin() + last + 1); for (int i = 0; i < n; i++) { cout << arr[i] << " "; } } } // Driver Code int main() { // Initialize the array arr[] vector<int> arr = { 1, 3, 4, 2, 5 }; int N = arr.size(); // Function call lexsmallest(arr, N); return 0; }
Java
// Java code for the above approach import java.util.*; class GFG{ // Function to find the // Lexicographically smallest // Permutation by one subarray reversal static void lexsmallest(int []arr, int n) { // Initialize the variables // To store the first and last // Position of the subarray int first = -1, flag = 0, find = -1, last = -1; // Traverse the array // And check if arr[i]!=i+1 for (int i = 0; i < n; i++) { if (arr[i] != i + 1) { flag = 1; // Mark the first position // Of the Subarray to be reversed first = i; find = i + 1; break; } } // If flag == 0, it is the // Smallest permutation, // So print the array if (flag == 0) { for (int i = 0; i < n; i++) { System.out.print(arr[i]+ " "); } } // Check where the minimum element is present else { for (int i = 0; i < n; i++) { // It is the last position // Of the subarray to be // Reversed if (arr[i] == find) { last = i; break; } } // Reverse the subarray // And print the array arr = reverse(arr,first,last); for (int i = 0; i < n; i++) { System.out.print(arr[i]+ " "); } } } static int[] reverse(int str[], int start, int end) { // Temporary variable to store character int temp; while (start <= end) { // Swapping the first and last character temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; } return str; } // Driver Code public static void main(String[] args) { // Initialize the array arr[] int []arr = { 1, 3, 4, 2, 5 }; int N = arr.length; // Function call lexsmallest(arr, N); } } // This code contributed by shikhasingrajput
Python3
# Python code for the above approach # Function to find the # Lexicographically smallest # Permutation by one subarray reversal def lexsmallest(arr, n): # Initialize the variables # To store the first and last # Position of the subarray first = -1 flag = 0 find = -1 last = -1 # Traverse the array # And check if arr[i]!=i+1 for i in range(0, n): if (arr[i] != i + 1): flag = 1 # Mark the first position # Of the Subarray to be reversed first = i find = i + 1 break # If flag == 0, it is the # Smallest permutation, # So print the array if (flag == 0): for i in range(0, n): print(arr[i], end=" ") # Check where the minimum element is present else: for i in range(0, n): # It is the last position # Of the subarray to be # Reversed if (arr[i] == find): last = i break # Reverse the subarray # And print the array arr[first: last + 1] = arr[first: last + 1][::-1] print(*arr) # Driver Code # Initialize the array arr[] arr = [1, 3, 4, 2, 5] N = len(arr) # Function call lexsmallest(arr, N) # This code is contributed by Samim Hossain Mondal.
C#
// C# code for the above approach using System; class GFG{ // Function to find the // Lexicographically smallest // Permutation by one subarray reversal static void lexsmallest(int []arr, int n) { // Initialize the variables // To store the first and last // Position of the subarray int first = -1, flag = 0, find = -1, last = -1; // Traverse the array // And check if arr[i]!=i+1 for (int i = 0; i < n; i++) { if (arr[i] != i + 1) { flag = 1; // Mark the first position // Of the Subarray to be reversed first = i; find = i + 1; break; } } // If flag == 0, it is the // Smallest permutation, // So print the array if (flag == 0) { for (int i = 0; i < n; i++) { Console.Write(arr[i]+ " "); } } // Check where the minimum element is present else { for (int i = 0; i < n; i++) { // It is the last position // Of the subarray to be // Reversed if (arr[i] == find) { last = i; break; } } // Reverse the subarray // And print the array arr = reverse(arr,first,last); for (int i = 0; i < n; i++) { Console.Write(arr[i]+ " "); } } } static int[] reverse(int[] str, int start, int end) { // Temporary variable to store character int temp; while (start <= end) { // Swapping the first and last character temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; } return str; } // Driver Code static public void Main (){ // Initialize the array arr[] int [] arr = { 1, 3, 4, 2, 5 }; int N = arr.Length; // Function call lexsmallest(arr, N); } } // This code is contributed by hrithikgarg03188.
Javascript
<script> // JavaScript code for the above approach // Function to find the // Lexicographically smallest // Permutation by one subarray reversal const lexsmallest = (arr, n) => { // Initialize the variables // To store the first and last // Position of the subarray let first = -1, flag = 0, find = -1, last = -1; // Traverse the array // And check if arr[i]!=i+1 for (let i = 0; i < n; i++) { if (arr[i] != i + 1) { flag = 1; // Mark the first position // Of the Subarray to be reversed first = i; find = i + 1; break; } } // If flag == 0, it is the // Smallest permutation, // So print the array if (flag == 0) { for (let i = 0; i < n; i++) { document.write(`${arr[i]} `); } } // Check where the minimum element is present else { for (let i = 0; i < n; i++) { // It is the last position // Of the subarray to be // Reversed if (arr[i] == find) { last = i; break; } } // Reverse the subarray // And print the array arr.splice(first, last, ...arr.slice(first, last + 1).reverse()); for (let i = 0; i < n; i++) { document.write(`${arr[i]} `); } } } // Driver Code // Initialize the array arr[] let arr = [1, 3, 4, 2, 5]; let N = arr.length; // Function call lexsmallest(arr, N); // This code is contributed by rakeshsahni </script>
1 2 4 3 5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA