Dada una array arr[] que representa una permutación de los primeros N números naturales , la tarea es encontrar la permutación lexicográficamente más pequeña posible de la array dada arr[] intercambiando como máximo un par de elementos de la array. Si no es posible hacer la array lexicográficamente más pequeña, imprima “-1” .
Ejemplos:
Entrada: arr[] = {3, 2, 1, 4}
Salida: 1 2 3 4
Explicación: intercambiando elementos en el índice 2 y 0, la array modificada es {1, 2, 3, 4}, que es lexicográficamente la más pequeña permutación de la array dada arr[].Entrada: arr[] = {1, 2, 3, 4}
Salida: -1
Enfoque: La idea es encontrar el primer elemento de la array que no está en su posición correcta, es decir, arr[i] no es lo mismo que el índice (i + 1) , e intercambiarlo con el elemento en su posición correcta. Siga los pasos a continuación para resolver este problema:
- Recorre la array arr[] y encuentra el índice i tal que arr[i] no es igual a (i + 1) , digamos idx , y almacena (i + 1) en una variable, digamos ele .
- Ahora, encuentre el índice de ele , digamos newIdx .
- Después de completar los pasos anteriores, existen dos índices idx y newIdx . La permutación lexicográficamente más pequeña de la array se puede formar intercambiando elementos en los índices idx y newIdx . Ahora, imprima la array arr[] . De lo contrario, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation of the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to print the
// elements of the array arr[]
void print(int arr[], int N)
{
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
// Function to convert given array to
// lexicographically smallest permutation
// possible by swapping at most one pair
void makeLexicographically(int arr[], int N)
{
// Stores the index of the first
// element which is not at its
// correct position
int index = 0;
int temp = 0;
// Checks if any such array
// element exists or not
int check = 0;
int condition = 0;
int element = 0;
// Traverse the given array
for (int i = 0; i < N; ++i) {
// If element is found at i
if (element == arr[i]) {
check = i;
break;
}
// If the first array is
// not in correct position
else if (arr[i] != i + 1 && check == 0) {
// Store the index of
// the first elements
index = i;
check = 1;
condition = -1;
// Store the index of
// the first element
element = i + 1;
}
}
// Swap the pairs
if (condition == -1) {
temp = arr[index];
arr[index] = arr[check];
arr[check] = temp;
}
// Print the array
print(arr, N);
}
// Driver code
int main()
{
// Given array
int arr[] = { 1, 2, 3, 4 };
// Store the size of the array
int N = sizeof(arr) / sizeof(arr[0]);
makeLexicographically(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to print the
// elements of the array arr[]
static void print(int arr[])
{
// Traverse the array arr[]
for (int element : arr) {
System.out.print(element + " ");
}
}
// Function to convert given array to
// lexicographically smallest permutation
// possible by swapping at most one pair
static void makeLexicographically(
int arr[], int length)
{
// Stores the index of the first
// element which is not at its
// correct position
int index = 0;
int temp = 0;
// Checks if any such array
// element exists or not
int check = 0;
int condition = 0;
int element = 0;
// Traverse the given array
for (int i = 0; i < length; ++i) {
// If element is found at i
if (element == arr[i]) {
check = i;
break;
}
// If the first array is
// not in correct position
else if (arr[i] != i + 1
&& check == 0) {
// Store the index of
// the first elements
index = i;
check = 1;
condition = -1;
// Store the index of
// the first element
element = i + 1;
}
}
// Swap the pairs
if (condition == -1) {
temp = arr[index];
arr[index] = arr[check];
arr[check] = temp;
}
// Print the array
print(arr);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4 };
int N = arr.length;
makeLexicographically(arr, N);
}
}
Python3
# Python3 program for the above approach # Function to print the # elements of the array arr[] def printt(arr, N) : # Traverse the array arr[] for i in range(N): print(arr[i], end = " ") # Function to convert given array to # lexicographically smallest permutation # possible by swapping at most one pair def makeLexicographically(arr, N) : # Stores the index of the first # element which is not at its # correct position index = 0 temp = 0 # Checks if any such array # element exists or not check = 0 condition = 0 element = 0 # Traverse the given array for i in range(N): # If element is found at i if (element == arr[i]) : check = i break # If the first array is # not in correct position elif (arr[i] != i + 1 and check == 0) : # Store the index of # the first elements index = i check = 1 condition = -1 # Store the index of # the first element element = i + 1 # Swap the pairs if (condition == -1) : temp = arr[index] arr[index] = arr[check] arr[check] = temp # Print the array printt(arr, N) # Driver code # Given array arr = [ 1, 2, 3, 4 ] # Store the size of the array N = len(arr) makeLexicographically(arr, N) # This code is contributed by code_hunt.
C#
// C# program for the above approach
using System;
class GFG {
// Function to print the
// elements of the array arr[]
static void print(int[] arr)
{
// Traverse the array arr[]
foreach (int element in arr) {
Console.Write(element + " ");
}
}
// Function to convert given array to
// lexicographically smallest permutation
// possible by swapping at most one pair
static void makeLexicographically(
int []arr, int length)
{
// Stores the index of the first
// element which is not at its
// correct position
int index = 0;
int temp = 0;
// Checks if any such array
// element exists or not
int check = 0;
int condition = 0;
int element = 0;
// Traverse the given array
for (int i = 0; i < length; ++i) {
// If element is found at i
if (element == arr[i]) {
check = i;
break;
}
// If the first array is
// not in correct position
else if (arr[i] != i + 1
&& check == 0) {
// Store the index of
// the first elements
index = i;
check = 1;
condition = -1;
// Store the index of
// the first element
element = i + 1;
}
}
// Swap the pairs
if (condition == -1) {
temp = arr[index];
arr[index] = arr[check];
arr[check] = temp;
}
// Print the array
print(arr);
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4 };
int N = arr.Length;
makeLexicographically(arr, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript implementation of the above approach
// Function to print the
// elements of the array arr[]
function print(arr, N)
{
// Traverse the array arr[]
for (i = 0; i < N; i++) {
document.write(arr[i]+ " ");
}
}
// Function to convert given array to
// lexicographically smallest permutation
// possible by swapping at most one pair
function makeLexicographically(arr, N)
{
// Stores the index of the first
// element which is not at its
// correct position
var index = 0;
var temp = 0;
// Checks if any such array
// element exists or not
var check = 0;
var condition = 0;
var element = 0;
// Traverse the given array
for (i = 0; i < N; ++i) {
// If element is found at i
if (element == arr[i]) {
check = i;
break;
}
// If the first array is
// not in correct position
else if (arr[i] != i + 1 && check == 0) {
// Store the index of
// the first elements
index = i;
check = 1;
condition = -1;
// Store the index of
// the first element
element = i + 1;
}
}
// Swap the pairs
if (condition == -1) {
temp = arr[index];
arr[index] = arr[check];
arr[check] = temp;
}
// Print the array
print(arr, N);
}
// Driver code
// Given array
var arr = [1, 2, 3, 4]
// Store the size of the array
var N = arr.length;
makeLexicographically(arr, N);
// This code is contributed by SURENDRA_GANGWAR.
</script>
Producción:
1 2 3 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA