Solución Java 1
public int minIncrementForUnique(int[] A) { Arrays.sort(A); int count = 0; for(int i=1; i<A.length; i++){ if(A[i]<=A[i-1]){ count+=A[i-1]+1; A[i]=A[i]+1; } } return count; } |
En realidad, no necesitamos incrementar el recuento en uno. Simplemente podemos hacer lo siguiente:
public int minIncrementForUnique(int[] A) { Arrays.sort(A); int count = 0; for(int i=1; i<A.length; i++){ if(A[i]<=A[i-1]){ count+=A[i-1]+1-A[i]; A[i]=A[i-1]+1; } } return count; } |
El tiempo es O (Nlog (N)).
Solución Java 2
Primero contamos el número usando una matriz de cubos. Para cada balde, si hay más de uno, lo registramos y cuando tengamos un balde vacío, lo colocamos allí.
public int minIncrementForUnique(int[] A) { int result = 0; int[] count = new int[100000]; for(int i: A){ count[i]++; } int dup = 0; for(int i=0; i<100000; i++){ if(count[i]>1){ result -= (count[i]-1)*i; dup += count[i]-1; }else if(count[i]==0 && dup>0){ result += i; dup--; } } return result; } |
El tiempo es O (N) y el espacio es O (N).
