Dada una array arr[] que consiste en N enteros, la tarea es encontrar la permutación lexicográficamente más grande posible de la array dada por exactamente un intercambio, que es más pequeño que la array dada. Si es posible obtener tal permutación, imprima esa permutación. De lo contrario, imprima «-1» .
Ejemplos:
Entrada: arr[] = {5, 4, 3, 2, 1}
Salida: 5 4 3 1 2
Explicación:
lexicográficamente, la permutación más grande que es más pequeña que la array dada se puede formar intercambiando 2 y 1.
Por lo tanto, la la permutación resultante es {5, 4, 3, 1, 2}Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: -1
Enfoque: el problema dado se puede resolver encontrando el último elemento que es mayor que su siguiente elemento e intercambiándolo con el siguiente elemento más pequeño en la array . Siga los pasos a continuación para resolver el problema:
- Si la array dada está ordenada en orden ascendente , imprima «-1» ya que no es posible encontrar lexicográficamente la permutación más grande de la array dada que es más pequeña que la array dada.
- Recorra la array dada desde el final y encuentre ese índice, digamos idx , que es estrictamente mayor que el siguiente elemento.
- Ahora, recorra nuevamente la array dada desde el final y encuentre el índice (digamos j ) del primer elemento, que es más pequeño, el elemento arr[idx] .
- Reducir el valor de j hasta que arr[j – 1] es lo mismo que arr[j] .
- Intercambie los elementos en el índice idx y j en la array arr[] para obtener la permutación resultante.
- Después de completar los pasos anteriores, imprima la array como la permutación resultante.
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 to lexicographic largest
// permutation possible by a swap
// that is smaller than given array
void findPermutation(vector<int>& arr)
{
int N = arr.size();
int i = N - 2;
// Find the index of first element
// such that arr[i] > arr[i + 1]
while (i >= 0 && arr[i] <= arr[i + 1])
i--;
// If the array is sorted
// in increasing order
if (i == -1) {
cout << "-1";
return;
}
int j = N - 1;
// Find the index of first element
// which is smaller than arr[i]
while (j > i && arr[j] >= arr[i])
j--;
// If arr[j] == arr[j-1]
while (j > i && arr[j] == arr[j - 1]) {
// Decrement j
j--;
}
// Swap the element
swap(arr[i], arr[j]);
// Print the array arr[]
for (auto& it : arr) {
cout << it << ' ';
}
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 5, 3, 4, 6 };
findPermutation(arr);
return 0;
}
Java
// java program for the above approach
import java.util.*;
class GFG{
// Function to lexicographic largest
// permutation possible by a swap
// that is smaller than given array
static void findPermutation(int[] arr)
{
int N = arr.length;
int i = N - 2;
// Find the index of first element
// such that arr[i] > arr[i + 1]
while (i >= 0 && arr[i] <= arr[i + 1])
i--;
// If the array is sorted
// in increasing order
if (i == -1)
{
System.out.print("-1");
return;
}
int j = N - 1;
// Find the index of first element
// which is smaller than arr[i]
while (j > i && arr[j] >= arr[i])
j--;
// If arr[j] == arr[j-1]
while (j > i && arr[j] == arr[j - 1])
{
// Decrement j
j--;
}
// Swap the element
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Print the array arr[]
for(int it : arr)
{
System.out.print(it + " ");
}
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 2, 5, 3, 4, 6 };
findPermutation(arr);
}
}
// This code is contributed by splevel62.
C#
// C# program for the above approach
using System;
class GFG{
// Function to lexicographic largest
// permutation possible by a swap
// that is smaller than given array
static void findPermutation(int[] arr)
{
int N = arr.Length;
int i = N - 2;
// Find the index of first element
// such that arr[i] > arr[i + 1]
while (i >= 0 && arr[i] <= arr[i + 1])
i--;
// If the array is sorted
// in increasing order
if (i == -1)
{
Console.Write("-1");
return;
}
int j = N - 1;
// Find the index of first element
// which is smaller than arr[i]
while (j > i && arr[j] >= arr[i])
j--;
// If arr[j] == arr[j-1]
while (j > i && arr[j] == arr[j - 1])
{
// Decrement j
j--;
}
// Swap the element
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Print the array arr[]
foreach(int it in arr)
{
Console.Write(it + " ");
}
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 5, 3, 4, 6 };
findPermutation(arr);
}
}
// This code is contributed by ukasp
Python3
# Python program for the above approach
# Function to lexicographic largest
# permutation possible by a swap
# that is smaller than given array
def findPermutation(arr):
N = len(arr)
i = N - 2
# Find the index of first element
# such that arr[i] > arr[i + 1]
while (i >= 0 and arr[i] <= arr[i + 1]):
i -= 1
# If the array is sorted
# in increasing order
if (i == -1) :
print("-1")
return
j = N - 1
# Find the index of first element
# which is smaller than arr[i]
while (j > i and arr[j] >= arr[i]):
j -= 1
# If arr[j] == arr[j-1]
while (j > i and arr[j] == arr[j - 1]) :
# Decrement j
j -= 1
# Swap the element
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
# Pr the array arr[]
for it in arr :
print(it, end = " ")
# Driver Code
arr = [ 1, 2, 5, 3, 4, 6 ]
findPermutation(arr)
# This code is contributed by code_hunt.
Javascript
<script>
// Javascript program for the above approach
// Function to lexicographic largest
// permutation possible by a swap
// that is smaller than given array
function findPermutation(arr)
{
let N = arr.length;
let i = N - 2;
// Find the index of first element
// such that arr[i] > arr[i + 1]
while (i >= 0 && arr[i] <= arr[i + 1])
i--;
// If the array is sorted
// in increasing order
if (i == -1)
{
document.write("-1");
return;
}
let j = N - 1;
// Find the index of first element
// which is smaller than arr[i]
while (j > i && arr[j] >= arr[i])
j--;
// If arr[j] == arr[j-1]
while (j > i && arr[j] == arr[j - 1])
{
// Decrement j
j--;
}
// Swap the element
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Print the array arr[]
for(let it in arr)
{
document.write(arr[it] + " ");
}
}
// Driver Code
let arr = [ 1, 2, 5, 3, 4, 6 ];
findPermutation(arr);
</script>
Producción:
1 2 4 3 5 6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rahulagarwal14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA