Operaciones de incremento mínimo para hacer que Array sea único

Dada una array A[] de enteros. En un movimiento, puede elegir cualquier elemento A[i] e incrementarlo en 1. La tarea es devolver el número mínimo de movimientos necesarios para que cada valor en la array A[] sea único.
Ejemplos : 
 

Input: A[] = [3, 2, 1, 2, 1, 7]
Output: 6
Explanation:  After 6 moves, the array could be 
[3, 4, 1, 2, 5, 7].
It can be shown that it is impossible for the array 
to have all unique values with 5 or less moves.

Input: A[] = [1, 2, 2]
Output: 1
Explanation: After 1 move [2 -> 3], the array could be [1, 2, 3].

Una solución simple para hacer que cada valor duplicado sea único es seguir incrementándolo repetidamente hasta que no sea único. Sin embargo, podríamos hacer mucho trabajo extra, si tenemos una array de todos unos.
Entonces, lo que podemos hacer en su lugar es evaluar cuáles deberían ser nuestros incrementos. Si, por ejemplo, tenemos [1, 1, 1, 3, 5], no necesitamos procesar todos los incrementos de 1 duplicados. Podríamos tomar dos unos (tomados = [1, 1]) y continuar procesando. Siempre que encontremos un lugar vacío (valor no utilizado) como 2 o 4, podemos recuperar que nuestro incremento será 2-1, 4-1 respectivamente.
Por lo tanto, primero contamos los valores y para cada posible valor X en la array: 
 

• Si hay 2 o más valores X en A, guarde los valores duplicados adicionales para incrementarlos más tarde.
• Si hay 0 valores X en A, entonces un valor guardado se incrementa a X.

A continuación se muestra la implementación del enfoque anterior: 
 

// Java Implementation of above approach
import java.util.*;
 
class GFG {
 
    // function to find minimum increment required
    static int minIncrementForUnique(int[] A)
    {
        // collect frequency of each element
        TreeMap<Integer, Integer> dict
            = new TreeMap<Integer, Integer>();
        HashSet<Integer> used = new HashSet<Integer>();
 
      // Load Frequency Map (Element -> Count) and Used Set
        for (int i : A) {
            if (dict.containsKey(i))
                dict.put(i, dict.get(i) + 1);
            else {
                dict.put(i, 1);
                used.add(i);
            }
        }
 
        int maxUsed = 0; // Works for +ve numbers
        int ans = 0;
 
        for (Map.Entry<Integer, Integer> entry :
             dict.entrySet()) {
 
            int value = entry.getKey();
            int freq = entry.getValue();
 
            if (freq <= 1) //If not a duplicate, skip
                continue;
 
            int duplicates = freq - 1; // Number of duplicates 1 less than count
           
          // Start with next best option for this duplicate:
          // CurNum + 1 or an earlier maximum number that has been used
            int cur = Math.max(value + 1, maxUsed);
            while (duplicates > 0) {
                if (!used.contains(cur)) {
                    ans += cur - value; // Number of increments = Available Spot - Duplicate Value
                    used.add(cur);
                    duplicates--;
                    maxUsed = cur;
                }
                cur++;
            }
        }
 
        // return answer
        return ans;
    }
 
    // Driver code
 
    public static void main(String[] args)
    {
        int[] A = { 3, 2, 1, 2, 1, 2, 6, 7 };
        System.out.print(minIncrementForUnique(A));
    }
}
 
// This code is contributed by Aditya

# Python3 Implementation of above approach
import collections
 
# function to find minimum increment required
def minIncrementForUnique(A):
 
    # collect frequency of each element
    count = collections.Counter(A)
 
    # array of unique values taken
    taken = []
 
    ans = 0
 
    for x in range(100000):
        if count[x] >= 2:
            taken.extend([x] * (count[x] - 1))
        elif taken and count[x] == 0:
            ans += x - taken.pop()
 
    # return answer
    return ans
 
# Driver code
A = [3, 2, 1, 2, 1, 7]
print(minIncrementForUnique(A))

// C# Implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG
{
  
// function to find minimum increment required
static int minIncrementForUnique(int []A)
{
  
    // collect frequency of each element
    Dictionary<int,int> mpp = new Dictionary<int,int>();
  
    foreach(int i in A)
    {
        if(mpp.ContainsKey(i))
            mpp[i] = mpp[i] + 1;
        else
            mpp.Add(i, 1);
    }
  
    // array of unique values taken
    List<int> taken = new List<int>();
  
    int ans = 0;
  
    for (int x = 0; x < 100000; x++)
    {
        if (mpp.ContainsKey(x) && mpp[x] >= 2)
            taken.Add(x * (mpp[x] - 1));
        else if(taken.Count > 0 &&
                ((mpp.ContainsKey(x) &&
                mpp[x] == 0)||!mpp.ContainsKey(x)))
        {
            ans += x - taken[taken.Count - 1];
            taken.RemoveAt(taken.Count - 1);
        }
    }
  
    // return answer
    return ans;
}
  
// Driver code
public static void Main(String[] args)
{
  
    int []A = {3, 2, 1, 2, 1, 7};
      
    Console.Write(minIncrementForUnique(A));
}
}
 
// This code contributed by PrinciRaj1992

12

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