Cambie la array a una permutación de números de 1 a n

Dada una array A de n elementos. Necesitamos cambiar la array a una permutación de números del 1 al n usando reemplazos mínimos en la array. 

Ejemplos: 

Input : A[] = {2, 2, 3, 3} 
Output : 2 1 3 4
Explanation:
To make it a permutation of 1 to 4, 1 and 4 are
missing from the array. So replace 2, 3 with 
1 and 4.

Input :  A[] = {1, 3, 2}
Output : 1 3 2

Input : A[] = {10, 1, 2}
Output : 3 1 2     

Enfoque: observe que no necesitamos cambiar los números que están en el rango [1, n] y que son distintos (solo tiene una aparición). Entonces, usamos un enfoque codicioso. Si encontramos el número que nunca antes habíamos conocido y este número está entre 1 y n, dejamos este número sin cambios. Y elimine los elementos duplicados y agregue los elementos faltantes en el rango [1, n]. También reemplace los números, no en el rango. 

Implementación:

// CPP program to make a permutation of numbers
// from 1 to n using minimum changes.
#include <bits/stdc++.h>
using namespace std;
 
void makePermutation(int a[], int n)
{
    // Store counts of all elements.
    unordered_map<int, int> count;
    for (int i = 0; i < n; i++)
        count[a[i]]++;
 
    int next_missing = 1;
    for (int i = 0; i < n; i++) {
        if (count[a[i]] != 1 || a[i] > n || a[i] < 1) {
            count[a[i]]--;
 
            // Find next missing element to put
            // in place of current element.
            while (count.find(next_missing) != count.end())
                next_missing++;
 
            // Replace with next missing and insert the
            // missing element in hash.
            a[i] = next_missing;
            count[next_missing] = 1;
        }
    }
}
 
// Driver Code
int main()
{
    int A[] = { 2, 2, 3, 3 };
    int n = sizeof(A) / sizeof(A[0]);
    makePermutation(A, n);
    for (int i = 0; i < n; i++)
        cout << A[i] << " ";
    return 0;
}

// Java program to make a permutation of numbers
// from 1 to n using minimum changes.
import java.util.*;
 
class GFG
{
static void makePermutation(int []a, int n)
{
    // Store counts of all elements.
    HashMap<Integer,
            Integer> count = new HashMap<Integer,
                                         Integer>();
    for (int i = 0; i < n; i++)
    {
        if(count.containsKey(a[i]))
        {
            count.put(a[i], count.get(a[i]) + 1);
        }
        else
        {
            count.put(a[i], 1);
        }
    }
 
    int next_missing = 1;
    for (int i = 0; i < n; i++)
    {
        if (count.containsKey(a[i]) &&
            count.get(a[i]) != 1 ||
            a[i] > n || a[i] < 1)
        {
            count.put(a[i], count.get(a[i]) - 1);
 
            // Find next missing element to put
            // in place of current element.
            while (count.containsKey(next_missing))
                next_missing++;
 
            // Replace with next missing and insert
            // the missing element in hash.
            a[i] = next_missing;
            count. put(next_missing, 1);
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 2, 2, 3, 3 };
    int n = A.length;
    makePermutation(A, n);
    for (int i = 0; i < n; i++)
        System.out.print(A[i] + " ");
    }
}
 
// This code is contributed by PrinciRaj1992

# Python3 code to make a permutation
# of numbers from 1 to n using
# minimum changes.
 
def makePermutation (a, n):
 
    # Store counts of all elements.
    count = dict()
    for i in range(n):
        if count.get(a[i]):
            count[a[i]] += 1
        else:
            count[a[i]] = 1;
         
    next_missing = 1
    for i in range(n):
        if count[a[i]] != 1 or a[i] > n or a[i] < 1:
            count[a[i]] -= 1
             
            # Find next missing element to put
            # in place of current element.
            while count.get(next_missing):
                next_missing+=1
             
            # Replace with next missing and
            # insert the missing element in hash.
            a[i] = next_missing
            count[next_missing] = 1
 
# Driver Code
A = [ 2, 2, 3, 3 ]
n = len(A)
makePermutation(A, n)
 
for i in range(n):
    print(A[i], end = " ")
     
# This code is contributed by "Sharad_Bhardwaj".

// C# program to make a permutation of numbers
// from 1 to n using minimum changes.
using System;
using System.Collections.Generic;
 
class GFG
{
static void makePermutation(int []a, int n)
{
    // Store counts of all elements.
    Dictionary<int,
               int> count = new Dictionary<int,
                                           int>();
    for (int i = 0; i < n; i++)
    {
        if(count.ContainsKey(a[i]))
        {
            count[a[i]] = count[a[i]] + 1;
        }
        else
        {
            count.Add(a[i], 1);
        }
    }
 
    int next_missing = 1;
    for (int i = 0; i < n; i++)
    {
        if (count.ContainsKey(a[i]) &&
            count[a[i]] != 1 ||
            a[i] > n || a[i] < 1)
        {
            count[a[i]] = count[a[i]] - 1;
 
            // Find next missing element to put
            // in place of current element.
            while (count.ContainsKey(next_missing))
                next_missing++;
 
            // Replace with next missing and insert
            // the missing element in hash.
            a[i] = next_missing;
            count.Add(next_missing, 1);
        }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 2, 2, 3, 3 };
    int n = A.Length;
    makePermutation(A, n);
    for (int i = 0; i < n; i++)
        Console.Write(A[i] + " ");
}
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program to make a permutation of numbers
// from 1 to n using minimum changes.
 
function makePermutation(a, n)
{
    // Store counts of all elements.
    var count = new Map();
    for(var i = 0; i < n; i++)
    {
        if(count.has(a[i]))
            count.set(a[i], count.get(a[i])+1)
        else
            count.set(a[i], 1)
    }
 
    var next_missing = 1;
    for (var i = 0; i < n; i++) {
        if (count.get(a[i]) != 1 || a[i] > n || a[i] < 1) {
 
            count.set(a[i], count.get(a[i])-1);
 
            // Find next missing element to put
            // in place of current element.
            while (count.has(next_missing))
                next_missing++;
 
            // Replace with next missing and insert the
            // missing element in hash.
            a[i] = next_missing;
            count.set(next_missing,1);
        }
    }
}
 
// Driver Code
 
var A = [2, 2, 3, 3];
var n = A.length;
makePermutation(A, n);
for(var i = 0; i < n; i++)
    document.write( A[i] + " ");
 
</script>

1 2 4 3 

Complejidad de tiempo: O(n log n)
Espacio auxiliar: O(n)

Este artículo es una contribución de Aarti_Rathi . 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.