Dado un entero K y un arreglo arr[] que tiene N enteros distintos por pares en el rango [1, K] , la tarea es encontrar la permutación lexicográficamente más pequeña de los primeros K enteros positivos tal que el arreglo dado arr[] sea una subsecuencia de la permutación.
Ejemplos:
Entrada: arr[] = {1, 3, 5, 7}, K = 8
Salida: 1 2 3 4 5 6 7 8
Explicación: {1, 2, 3, 4, 5, 6, 7, 8} es el permutación lexicográficamente más pequeña de los primeros 8 enteros positivos tal que la array dada {1, 3, 5, 7} también es una subsecuencia de la permutación.Entrada: arr[] = {6, 4, 2, 1}, K=7
Salida: 3 5 6 4 2 1 7
Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . A continuación se detallan los pasos a seguir:
- Cree un vector que falta[] que almacene los enteros en el rango [1, K] en orden creciente que no están presentes en la array dada arr[] usando el enfoque que se describe en este artículo .
- Cree dos punteros p1 y p2 que almacenen el índice actual en arr[] y faltante[] respectivamente. Inicialmente, ambos son iguales a 0 .
- Codiciosamente, tome y almacene el mínimo de arr[p1] y falta [p2] en un vector, diga ans[] e incremente el puntero respectivo a la siguiente posición hasta que el recuento de los enteros almacenados sea menor que K .
- Para facilitar las cosas, agregue INT_MAX al final de la array que falta [] y arr [] , lo que evitará salirse de los límites.
- Después de completar los pasos anteriores, todos los valores almacenados en ans[] son el resultado requerido.
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 find the lexicographically
// smallest permutation such that the
// given array is a subsequence of it
void findPermutation(int K, vector<int> arr)
{
// Stores the missing elements in
// arr in the range [1, K]
vector<int> missing;
// Stores if the ith element is
// present in arr or not
vector<bool> visited(K + 1, 0);
// Loop to mark all integers present
// in the array as visited
for (int i = 0; i < arr.size(); i++) {
visited[arr[i]] = 1;
}
// Loop to insert all the integers
// not visited into missing
for (int i = 1; i <= K; i++) {
if (!visited[i]) {
missing.push_back(i);
}
}
// Append INT_MAX at end in order
// to prevent going out of bounds
arr.push_back(INT_MAX);
missing.push_back(INT_MAX);
// Pointer to the current element
int p1 = 0;
// Pointer to the missing element
int p2 = 0;
// Stores the required permutation
vector<int> ans;
// Loop to construct the permutation
// using greedy approach
while (ans.size() < K) {
// If missing element is smaller
// that the current element insert
// missing element
if (arr[p1] < missing[p2]) {
ans.push_back(arr[p1]);
p1++;
}
// Insert current element
else {
ans.push_back(missing[p2]);
p2++;
}
}
// Print the required Permutation
for (int i = 0; i < K; i++) {
cout << ans[i] << " ";
}
}
// Driver Code
int main()
{
int K = 7;
vector<int> arr = { 6, 4, 2, 1 };
// Function Call
findPermutation(K, arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the lexicographically
// smallest permutation such that the
// given array is a subsequence of it
static void findPermutation(int K, Vector<Integer> arr)
{
// Stores the missing elements in
// arr in the range [1, K]
Vector<Integer> missing = new Vector<Integer>();
// Stores if the ith element is
// present in arr or not
boolean visited[] = new boolean[K + 1];
// Loop to mark all integers present
// in the array as visited
for (int i = 0; i < arr.size(); i++) {
visited[arr.get(i)] = true;
}
// Loop to insert all the integers
// not visited into missing
for (int i = 1; i <= K; i++) {
if (!visited[i]) {
missing.add(i);
}
}
// Append Integer.MAX_VALUE at end in order
// to prevent going out of bounds
arr.add(Integer.MAX_VALUE);
missing.add(Integer.MAX_VALUE);
// Pointer to the current element
int p1 = 0;
// Pointer to the missing element
int p2 = 0;
// Stores the required permutation
Vector<Integer> ans = new Vector<Integer>();
// Loop to construct the permutation
// using greedy approach
while (ans.size() < K) {
// If missing element is smaller
// that the current element insert
// missing element
if (arr.get(p1) < missing.get(p2)) {
ans.add(arr.get(p1));
p1++;
}
// Insert current element
else {
ans.add(missing.get(p2));
p2++;
}
}
// Print the required Permutation
for (int i = 0; i < K; i++) {
System.out.print(ans.get(i)+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
int K = 7;
Integer []a = {6, 4, 2, 1};
Vector<Integer> arr = new Vector<>(Arrays.asList(a));
// Function Call
findPermutation(K, arr);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach # Function to find the lexicographically # smallest permutation such that the # given array is a subsequence of it def findPermutation(K, arr): # Stores the missing elements in # arr in the range [1, K] missing = [] # Stores if the ith element is # present in arr or not visited = [0]*(K+1) # Loop to mark all integers present # in the array as visited for i in range(4): visited[arr[i]] = 1 # Loop to insert all the integers # not visited into missing for i in range(1, K+1): if(not visited[i]): missing.append(i) # Append INT_MAX at end in order # to prevent going out of bounds INT_MAX = 2147483647 arr.append(INT_MAX) missing.append(INT_MAX) # Pointer to the current element p1 = 0 # Pointer to the missing element p2 = 0 # Stores the required permutation ans = [] # Loop to construct the permutation # using greedy approach while (len(ans) < K): # If missing element is smaller # that the current element insert # missing element if (arr[p1] < missing[p2]): ans.append(arr[p1]) p1 = p1 + 1 # Insert current element else: ans.append(missing[p2]) p2 = p2 + 1 # Print the required Permutation for i in range(0, K): print(ans[i], end=" ") # Driver Code if __name__ == "__main__": K = 7 arr = [6, 4, 2, 1] # Function Call findPermutation(K, arr) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG{
// Function to find the lexicographically
// smallest permutation such that the
// given array is a subsequence of it
static void findPermutation(int K, ArrayList arr)
{
// Stores the missing elements in
// arr in the range [1, K]
ArrayList missing = new ArrayList();
// Stores if the ith element is
// present in arr or not
bool [] visited = new bool[K + 1];
// Loop to mark all integers present
// in the array as visited
for (int i = 0; i < arr.Count; i++) {
visited[(int)arr[i]] = true;
}
// Loop to insert all the integers
// not visited into missing
for (int i = 1; i <= K; i++) {
if (!visited[i]) {
missing.Add(i);
}
}
// Append Int32.MaxValue at end in order
// to prevent going out of bounds
arr.Add(Int32.MaxValue);
missing.Add(Int32.MaxValue);
// Pointer to the current element
int p1 = 0;
// Pointer to the missing element
int p2 = 0;
// Stores the required permutation
ArrayList ans = new ArrayList();
// Loop to construct the permutation
// using greedy approach
while (ans.Count < K) {
// If missing element is smaller
// that the current element insert
// missing element
if ((int)arr[p1] < (int)missing[p2]) {
ans.Add(arr[p1]);
p1++;
}
// Insert current element
else {
ans.Add(missing[p2]);
p2++;
}
}
// Print the required Permutation
for (int i = 0; i < K; i++) {
Console.Write(ans[i]+ " ");
}
}
// Driver Code
public static void Main()
{
int K = 7;
int [] a = {6, 4, 2, 1};
ArrayList arr = new ArrayList(a);
// Function Call
findPermutation(K, arr);
}
}
// This code is contributed by ihritik.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the lexicographically
// smallest permutation such that the
// given array is a subsequence of it
const findPermutation = (K, arr) => {
// Stores the missing elements in
// arr in the range [1, K]
let missing = [];
// Stores if the ith element is
// present in arr or not
let visited = new Array(K + 1).fill(0);
// Loop to mark all integers present
// in the array as visited
for (let i = 0; i < arr.length; i++) {
visited[arr[i]] = 1;
}
// Loop to insert all the integers
// not visited into missing
for (let i = 1; i <= K; i++) {
if (!visited[i]) {
// missing.push_back(i);
missing.push(i);
}
}
// Append INT_MAX at end in order
// to prevent going out of bounds
const INT_MAX = 2147483647;
arr.push(INT_MAX);
missing.push(INT_MAX);
// Pointer to the current element
let p1 = 0;
// Pointer to the missing element
let p2 = 0;
// Stores the required permutation
let ans = [];
// Loop to construct the permutation
// using greedy approach
while (ans.length < K) {
// If missing element is smaller
// that the current element insert
// missing element
if (arr[p1] < missing[p2]) {
ans.push(arr[p1]);
p1++;
}
// Insert current element
else {
ans.push(missing[p2]);
p2++;
}
}
// Print the required Permutation
for (let i = 0; i < K; i++) {
document.write(`${ans[i]} `);
}
}
// Driver Code
let K = 7;
let arr = [6, 4, 2, 1];
// Function Call
findPermutation(K, arr);
// This code is contributed by rakeshsahni.
</script>
Producción:
3 5 6 4 2 1 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA