Dada una array de n enteros positivos tal que cada elemento de un entero es de 1 a n. Encuentre la permutación lexicográfica que se puede obtener al reemplazar el número mínimo de elementos en una array de manera que cada elemento de la array ocurra exactamente una vez en la array completa. Primero, imprima el número mínimo de reemplazos necesarios y luego imprima la array lexicográfica final.
Ejemplos:
Input arr[] = {2, 3, 4, 3, 2}
Output 2
1 3 4 5 2
Explanation
Replace number '2' at position 1st with number
'1' and '3' at position 4th with number '5'.
The array that we obtain is [1, 3, 4, 5, 2]
which is lexicographically smallest among all
the possible suitable.
Input arr[] = {2, 1, 2, 1, 2}
Output 3
2 1 3 4 5
El enfoque ingenuo es generar toda la permutación de 1 a n y elegir la más pequeña que produzca los reemplazos mínimos. La complejidad de tiempo de este enfoque es O(n!) que definitivamente expirará para un gran valor de n.
El enfoque eficiente es elegir los elementos deseados con avidez. En primer lugar, inicialice la array cnt[] que contendrá la frecuencia de los elementos que aparecen en la array. Para cada elemento de la array (a i ), que se produjo más de una vez en una array, agregue los números en orden ascendente para obtener una permutación lexicográficamente mínima. Por ejemplo,
iterar la array sobre todos los elementos. Deje que el número actual de array sea a i . Si el recuento de a i es igual a 1, pase al siguiente número de la array. Si el recuento de a i es mayor que 1, reemplace el número a i con el elemento ele (el número más pequeño que no aparece en la array) solo si ele < a i. Mientras tanto, disminuya la cuenta de ai en la array cnt[].
Si ele > ai , marque el número ai para que podamos reemplazarlo en la próxima iteración. Este paso es necesario porque necesitamos hacer la permutación lexicográfica más pequeña .
For example, let's suppose the arr[] = {1, 5, 4, 5, 3, 7, 3}
In first iteration '5' occurs two times in array(indexing 1),
therefore we have to replace '5' at position '2' with '2'(2 < 5).
Now the updated array = {1, 2, 4, 5, 3, 7, 3}
In next iteration, '3' would be consider as it occurs two times
in array. But this time the next element of replacement would
be equals to 6 which is greater than 3. Therefore visit element
3 in boolean array vis[] and iterate over other elements.
Now again '3' occurred at position 7th, this time replace it with
number '6'.
Final array is arr[] = {1, 2, 4, 5, 3, 7, 6}
Implementación:
C++
// C++ program to print lexicographically
// permutation array by replacing minimum
// element of array
#include <bits/stdc++.h>
using namespace std;
// Function to calculate lexicographically permutation
// in array
void lexicoSmallestPermuatation(int arr[], int n)
{
// Calculate frequency of array elements
int cnt[n + 1];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i)
++cnt[arr[i]];
int ele = 1, replacement = 0;
bool vis[n + 1];
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; ++i) {
// If count of element is 1, no
// need to replace
if (cnt[arr[i]] == 1)
continue;
// Find the element that has not
// occurred in array
while (cnt[ele])
++ele;
// If replacement element is greater
// than current arr[i] then visit
// that element for next iteration
if (ele > arr[i] && !vis[arr[i]])
vis[arr[i]] = 1;
else {
// Decrement count and assign the element
// to array
--cnt[arr[i]];
arr[i] = ele;
// Increment the replacement count
++replacement;
// Increment element after assigning
// to the array
++ele;
}
}
cout << replacement << "\n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 3, 2 };
int sz = sizeof(arr) / sizeof(arr[0]);
lexicoSmallestPermuatation(arr, sz);
return 0;
}
Java
// Java program to print lexicographically
// permutation array by replacing minimum
// element of array
class GFG {
// Function to calculate lexicographically permutation
// in array
static void lexicoSmallestPermuatation(int arr[], int n) {
// Calculate frequency of array elements
int cnt[] = new int[n + 1];
for (int i = 0; i < n; ++i) {
++cnt[arr[i]];
}
int ele = 1, replacement = 0;
boolean vis[] = new boolean[n + 1];
for (int i = 0; i < n; ++i) {
// If count of element is 1, no
// need to replace
if (cnt[arr[i]] == 1) {
continue;
}
// Find the element that has not
// occurred in array
while (cnt[ele]>0) {
++ele;
}
// If replacement element is greater
// than current arr[i] then visit
// that element for next iteration
if (ele > arr[i] && !vis[arr[i]]) {
vis[arr[i]] = true;
} else {
// Decrement count and assign the element
// to array
--cnt[arr[i]];
arr[i] = ele;
// Increment the replacement count
++replacement;
// Increment element after assigning
// to the array
++ele;
}
}
System.out.print(replacement + "\n");
for (int i = 0; i < n; ++i) {
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main(String[] args) {
int arr[] = {2, 3, 4, 3, 2};
int sz = arr.length;
lexicoSmallestPermuatation(arr, sz);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to print lexicographically # permutation array by replacing minimum # element of array # Function to calculate lexicographically # permutation in array def lexicoSmallestPermuatation(arr, n): # Calculate frequency of array elements cnt = [0 for i in range(n + 1)] for i in range(n): cnt[arr[i]] += 1 ele = 1 replacement = 0 vis = [0 for i in range(n + 1)] for i in range(n): # If count of element is 1, no # need to replace if (cnt[arr[i]] == 1): continue # Find the element that has not # occurred in array while (cnt[ele]): ele += 1 # If replacement element is greater # than current arr[i] then visit # that element for next iteration if (ele > arr[i] and vis[arr[i]] == 0): vis[arr[i]] = 1; else: # Decrement count and assign # the element to array cnt[arr[i]] -= 1 arr[i] = ele # Increment the replacement count replacement += 1 # Increment element after assigning # to the array ele += 1 print(replacement) for i in range(n): print(arr[i], end = " ") # Driver code if __name__ == '__main__': arr = [2, 3, 4, 3, 2] sz = len(arr) lexicoSmallestPermuatation(arr, sz) # This code is contributed by # Shashank_Sharma
C#
// C# program to print lexicographically
// permutation array by replacing minimum
// element of array
using System;
public class GFG {
// Function to calculate lexicographically permutation
// in array
static void lexicoSmallestPermuatation(int []arr, int n) {
// Calculate frequency of array elements
int []cnt= new int[n + 1];
for (int i = 0; i < n; ++i) {
++cnt[arr[i]];
}
int ele = 1, replacement = 0;
bool []vis = new bool[n + 1];
for (int i = 0; i < n; ++i) {
// If count of element is 1, no
// need to replace
if (cnt[arr[i]] == 1) {
continue;
}
// Find the element that has not
// occurred in array
while (cnt[ele]>0) {
++ele;
}
// If replacement element is greater
// than current arr[i] then visit
// that element for next iteration
if (ele > arr[i] && !vis[arr[i]]) {
vis[arr[i]] = true;
} else {
// Decrement count and assign the element
// to array
--cnt[arr[i]];
arr[i] = ele;
// Increment the replacement count
++replacement;
// Increment element after assigning
// to the array
++ele;
}
}
Console.Write(replacement + "\n");
for (int i = 0; i < n; ++i) {
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main() {
int []arr = {2, 3, 4, 3, 2};
int sz = arr.Length;
lexicoSmallestPermuatation(arr, sz);
}
}
// This code is contributed by Rajput-Ji//
PHP
<?php
// PHP program to print lexicographically
// permutation array by replacing minimum
// element of array
// Function to calculate lexicographically
// permutation in array
function lexicoSmallestPermuatation(&$arr, $n)
{
// Calculate frequency of array elements
$cnt = array_fill(0, $n + 1, NULL);
for ($i = 0; $i < $n; ++$i)
++$cnt[$arr[$i]];
$ele = 1;
$replacement = 0;
$vis = array_fill(0, $n + 1, NULL);
for ($i = 0; $i < $n; ++$i)
{
// If count of element is 1, no
// need to replace
if ($cnt[$arr[$i]] == 1)
continue;
// Find the element that has not
// occurred in array
while ($cnt[$ele])
++$ele;
// If replacement element is greater
// than current arr[i] then visit
// that element for next iteration
if ($ele > $arr[$i] && !$vis[$arr[$i]])
$vis[$arr[$i]] = 1;
else
{
// Decrement count and assign the
// element to array
--$cnt[$arr[$i]];
$arr[$i] = $ele;
// Increment the replacement count
++$replacement;
// Increment element after assigning
// to the array
++$ele;
}
}
echo $replacement. "\n";
for ($i = 0; $i < $n; ++$i)
echo $arr[$i] . " ";
}
// Driver code
$arr = array(2, 3, 4, 3, 2 );
$sz = sizeof($arr);
lexicoSmallestPermuatation($arr, $sz);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to
// print lexicographically
// permutation array by
// replacing minimum
// element of array
// Function to calculate
// lexicographically permutation
// in array
function lexicoSmallestPermuatation(arr, n)
{
// Calculate frequency of
// array elements
let cnt = Array.from({length: n + 1},
(_, i) => 0);
for (let i = 0; i < n; ++i)
{
++cnt[arr[i]];
}
let ele = 1, replacement = 0;
let vis = Array.from({length: n + 1},
(_, i) => 0);
for (let i = 0; i < n; ++i) {
// If count of element is 1, no
// need to replace
if (cnt[arr[i]] == 1) {
continue;
}
// Find the element that has not
// occurred in array
while (cnt[ele]>0) {
++ele;
}
// If replacement element is greater
// than current arr[i] then visit
// that element for next iteration
if (ele > arr[i] && !vis[arr[i]]) {
vis[arr[i]] = true;
} else {
// Decrement count and
// assign the element
// to array
--cnt[arr[i]];
arr[i] = ele;
// Increment the
// replacement count
++replacement;
// Increment element
// after assigning
// to the array
++ele;
}
}
document.write(replacement + "<br/>");
for (let i = 0; i < n; ++i) {
document.write(arr[i] + " ");
}
}
// driver program
let arr = [2, 3, 4, 3, 2];
let sz = arr.length;
lexicoSmallestPermuatation(arr, sz);
</script>
Producción
2 1 3 4 5 2
Complejidad temporal: O(n)
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA