Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la permutación de los primeros N números naturales de modo que la array dada arr[] sea la array máxima de prefijos de esa permutación. Si no existe tal permutación, imprima “-1” .
Ejemplos:
Entrada: arr[] = {1, 3, 4, 5, 5}
Salida: 1 3 4 5 2
Explicación:
La array máxima de prefijos de la permutación {1, 3, 4, 5, 2} es {1, 3, 4, 5, 5}.Entrada: arr[] = {1, 1, 3, 4}
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las permutaciones posibles de los primeros N números naturales y verificar si existe alguna permutación cuyo arreglo máximo de prefijos sea el arreglo arr[] o no. Si se encuentra alguna de esas permutaciones, imprima esa permutación. De lo contrario, imprima «-1» .
Complejidad temporal: O(N * N!)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar basándose en la observación de que la primera aparición de cada número en el arr[] estará en el mismo lugar que en la permutación requerida. Por lo tanto, después de completar la primera ocurrencia de todos los elementos en sus posiciones correctas, complete los números restantes en orden ascendente. Siga los pasos a continuación para resolver el problema:
- Inicialice una array ans[] de tamaño N con todos los elementos como 0 y un vector V[] para almacenar todos los elementos no visitados en la array.
- Inicialice un HashMap M para almacenar el índice de la primera aparición de elementos
- Recorra la array arr[] y si arr[i] no está presente en M , almacene el índice de arr[i] en M y actualice ans[i] a arr[i] .
- Itere sobre el rango [1, N] usando la variable i y verifique si i no está presente en M , guárdelo en el vector V[] .
- Recorra la array ans[] y si el valor de ans[i] es 0 , actualice ans[i] a V[j] e incremente j en 1 .
- Después de completar los pasos anteriores, verifique si la array de prefijos de elementos máxima es la misma que arr[] . Si se determina que es cierto, imprima la array ans[] como resultado. De lo contrario, imprima «-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 to check if the maximum
// prefix array of ans[] is equal
// to array arr[]
bool checkPermutation(
int ans[], int a[], int n)
{
// Initialize a variable, Max
int Max = INT_MIN;
// Traverse the array, ans[]
for (int i = 0; i < n; i++) {
// Store the maximum value
// upto index i
Max = max(Max, ans[i]);
// If it is not equal to a[i],
// then return false
if (Max != a[i])
return false;
}
// Otherwise return false
return true;
}
// Function to find the permutation of
// the array whose prefix maximum array
// is same as the given array a[]
void findPermutation(int a[], int n)
{
// Stores the required permutation
int ans[n] = { 0 };
// Stores the index of first
// occurrence of elements
unordered_map<int, int> um;
// Traverse the array a[]
for (int i = 0; i < n; i++) {
// If a[i] is not present
// in um, then store it in um
if (um.find(a[i]) == um.end()) {
// Update the ans[i]
// to a[i]
ans[i] = a[i];
um[a[i]] = i;
}
}
// Stores the unvisited numbers
vector<int> v;
int j = 0;
// Fill the array, v[]
for (int i = 1; i <= n; i++) {
// Store the index
if (um.find(i) == um.end()) {
v.push_back(i);
}
}
// Traverse the array, ans[]
for (int i = 0; i < n; i++) {
// Fill v[j] at places where
// ans[i] is 0
if (ans[i] == 0) {
ans[i] = v[j];
j++;
}
}
// Check if the current permutation
// maximum prefix array is same as
// the given array a[]
if (checkPermutation(ans, a, n)) {
// If true, the print the
// permutation
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
}
// Otherwise, print -1
else
cout << "-1";
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 4, 5, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
findPermutation(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if the maximum
// prefix array of ans[] is equal
// to array arr[]
static boolean checkPermutation(int ans[], int a[],
int n)
{
// Initialize a variable, Max
int Max = Integer.MIN_VALUE;
// Traverse the array, ans[]
for(int i = 0; i < n; i++)
{
// Store the maximum value
// upto index i
Max = Math.max(Max, ans[i]);
// If it is not equal to a[i],
// then return false
if (Max != a[i])
return false;
}
// Otherwise return false
return true;
}
// Function to find the permutation of
// the array whose prefix maximum array
// is same as the given array a[]
static void findPermutation(int a[], int n)
{
// Stores the required permutation
int ans[] = new int[n];
// Stores the index of first
// occurrence of elements
HashMap<Integer, Integer> um = new HashMap<>();
// Traverse the array a[]
for(int i = 0; i < n; i++)
{
// If a[i] is not present
// in um, then store it in um
if (!um.containsKey(a[i]))
{
// Update the ans[i]
// to a[i]
ans[i] = a[i];
um.put(a[i], i);
}
}
// Stores the unvisited numbers
ArrayList<Integer> v = new ArrayList<>();
int j = 0;
// Fill the array, v[]
for(int i = 1; i <= n; i++)
{
// Store the index
if (!um.containsKey(i))
{
v.add(i);
}
}
// Traverse the array, ans[]
for(int i = 0; i < n; i++)
{
// Fill v[j] at places where
// ans[i] is 0
if (ans[i] == 0)
{
ans[i] = v.get(j);
j++;
}
}
// Check if the current permutation
// maximum prefix array is same as
// the given array a[]
if (checkPermutation(ans, a, n))
{
// If true, the print the
// permutation
for(int i = 0; i < n; i++)
{
System.out.print(ans[i] + " ");
}
}
// Otherwise, print -1
else
System.out.println("-1");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 3, 4, 5, 5 };
int N = arr.length;
// Function Call
findPermutation(arr, N);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
import sys
# Function to check if the maximum
# prefix array of ans[] is equal
# to array arr[]
def checkPermutation(ans, a, n):
# Initialize a variable, Max
Max = -sys.maxsize - 1
# Traverse the array, ans[]
for i in range(n):
# Store the maximum value
# upto index i
Max = max(Max, ans[i])
# If it is not equal to a[i],
# then return false
if (Max != a[i]):
return False
# Otherwise return false
return True
# Function to find the permutation of
# the array whose prefix maximum array
# is same as the given array a[]
def findPermutation(a, n):
# Stores the required permutation
ans = [0] * n
# Stores the index of first
# occurrence of elements
um = {}
# Traverse the array a[]
for i in range(n):
# If a[i] is not present
# in um, then store it in um
if (a[i] not in um):
# Update the ans[i]
# to a[i]
ans[i] = a[i]
um[a[i]] = i
# Stores the unvisited numbers
v = []
j = 0
# Fill the array, v[]
for i in range(1, n + 1):
# Store the index
if (i not in um):
v.append(i)
# Traverse the array, ans[]
for i in range(n):
# Fill v[j] at places where
# ans[i] is 0
if (ans[i] == 0):
ans[i] = v[j]
j += 1
# Check if the current permutation
# maximum prefix array is same as
# the given array a[]
if (checkPermutation(ans, a, n)):
# If true, the print the
# permutation
for i in range(n):
print(ans[i], end = " ")
# Otherwise, print -1
else:
print("-1")
# Driver Code
if __name__ == "__main__":
arr = [ 1, 3, 4, 5, 5 ]
N = len(arr)
# Function Call
findPermutation(arr, N)
# This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if the maximum
// prefix array of ans[] is equal
// to array arr[]
static bool checkPermutation(int[] ans, int[] a,
int n)
{
// Initialize a variable, Max
int Max = Int32.MinValue;
// Traverse the array, ans[]
for(int i = 0; i < n; i++)
{
// Store the maximum value
// upto index i
Max = Math.Max(Max, ans[i]);
// If it is not equal to a[i],
// then return false
if (Max != a[i])
return false;
}
// Otherwise return false
return true;
}
// Function to find the permutation of
// the array whose prefix maximum array
// is same as the given array a[]
static void findPermutation(int[] a, int n)
{
// Stores the required permutation
int[] ans = new int[n];
// Stores the index of first
// occurrence of elements
Dictionary<int,
int> um = new Dictionary<int,
int>();
// Traverse the array a[]
for(int i = 0; i < n; i++)
{
// If a[i] is not present
// in um, then store it in um
if (!um.ContainsKey(a[i]))
{
// Update the ans[i]
// to a[i]
ans[i] = a[i];
um[a[i]] = i;
}
}
// Stores the unvisited numbers
List<int> v = new List<int>();
int j = 0;
// Fill the array, v[]
for(int i = 1; i <= n; i++)
{
// Store the index
if (!um.ContainsKey(i))
{
v.Add(i);
}
}
// Traverse the array, ans[]
for(int i = 0; i < n; i++)
{
// Fill v[j] at places where
// ans[i] is 0
if (ans[i] == 0)
{
ans[i] = v[j];
j++;
}
}
// Check if the current permutation
// maximum prefix array is same as
// the given array a[]
if (checkPermutation(ans, a, n))
{
// If true, the print the
// permutation
for(int i = 0; i < n; i++)
{
Console.Write(ans[i] + " ");
}
}
// Otherwise, print -1
else
Console.Write("-1");
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 3, 4, 5, 5 };
int N = arr.Length;
// Function Call
findPermutation(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program for the above approach
// Function to check if the maximum
// prefix array of ans[] is equal
// to array arr[]
function checkPermutation(ans,a,n)
{
// Initialize a variable, Max
let Max = Number.MIN_VALUE;
// Traverse the array, ans[]
for(let i = 0; i < n; i++)
{
// Store the maximum value
// upto index i
Max = Math.max(Max, ans[i]);
// If it is not equal to a[i],
// then return false
if (Max != a[i])
return false;
}
// Otherwise return false
return true;
}
// Function to find the permutation of
// the array whose prefix maximum array
// is same as the given array a[]
function findPermutation(a,n)
{
// Stores the required permutation
let ans = new Array(n);
for(let i=0;i<n;i++)
{
ans[i]=0;
}
// Stores the index of first
// occurrence of elements
let um = new Map();
// Traverse the array a[]
for(let i = 0; i < n; i++)
{
// If a[i] is not present
// in um, then store it in um
if (!um.has(a[i]))
{
// Update the ans[i]
// to a[i]
ans[i] = a[i];
um.set(a[i], i);
}
}
// Stores the unvisited numbers
let v = [];
let j = 0;
// Fill the array, v[]
for(let i = 1; i <= n; i++)
{
// Store the index
if (!um.has(i))
{
v.push(i);
}
}
// Traverse the array, ans[]
for(let i = 0; i < n; i++)
{
// Fill v[j] at places where
// ans[i] is 0
if (ans[i] == 0)
{
ans[i] = v[j];
j++;
}
}
// Check if the current permutation
// maximum prefix array is same as
// the given array a[]
if (checkPermutation(ans, a, n))
{
// If true, the print the
// permutation
for(let i = 0; i < n; i++)
{
document.write(ans[i] + " ");
}
}
// Otherwise, print -1
else
document.write("-1");
}
// Driver Code
let arr=[1, 3, 4, 5, 5];
let N = arr.length;
// Function Call
findPermutation(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 3 4 5 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por utkershgahoi140 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA