使数组唯一的最小增量

题目

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。

返回使 A 中的每个值都是唯一的最少操作次数。

示例 1:

输入：[1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

示例 2:

输入：[3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

提示：

0 <= A.length <= 40000
0 <= A[i] < 40000

思路

简单的思路就是以空间换时间.将所有数组存入数组,然后比较后面的值即可.数组的范围有个坑.不能是40000.因为极端情况下数组可能是40000个39999,所以自增后最大值会到79999.所以需要将范围设置为80000.

当然上述的算法的时间复杂度很高.也可以进行优化.简单算法的思路是每次碰到有重复的就去后面寻找.其实不需要,如果有重复的,就先记录需要修改的个数.同时先减去需要修改的值.比如说有三个2,那么要改的值其实是3-2+4-2,也就是当碰到有重复值时先减去多余的值,后面碰到没有重复的时候再加上即可.最后需要修改的个数为0即可.

代码

简单算法

class Solution {
    public int minIncrementForUnique(int[] A) {
        //最小增量.因为题目有约定长度及大小.可以将所有数都存在数组中,
        int[] temp = new int[80000];
        for(int i = 0;i < A.length;i++){
            temp[A[i]]++;
        }
        int result = 0;
        for(int i = 0;i < temp.length;i++){
            if(temp[i] > 1){
                for(int j = i+1;j < temp.length;j++){
                    if(temp[j] == 0){
                        temp[j] = 1;
                        result+=j-i;
                        temp[i]--;
                    }
                    if(temp[i] == 1){
                        break;
                    }
                }
            }
        }
        return result;
    }
}

优化算法

class Solution {
    public int minIncrementForUnique(int[] A) {
        //最小增量.因为题目有约定长度及大小.可以将所有数都存在数组中,
        int[] temp = new int[60000];
        for(int i = 0;i < A.length;i++){
            temp[A[i]]++;
        }
        int result = 0;
        int num = 0;
        for(int i = 0;i <temp.length;i++){
            if(temp[i] > 1){
                num +=temp[i]-1;
                result -=i*(temp[i]-1);
            }else if(num > 0 && temp[i] == 0){
                num--;
                result += i;
            }
        }
        return result;
    }
}