使数组唯一的最小增量.md

题目：给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。返回使 A 中的每个值都是唯一的最少操作次数。

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

解法一

分析：对数组进行排序，从左到右遍历数组，并记录下当前数组的最后一个值（排序后为最大值）。如果当前位置的值等于这个最大的值，则说明存在冲突，需要移动，移动的值为最大值加1后减去当前位置的值，并修改最大的值。

1. 排序，得到[1,1,2,2,3,7]
2. 遍历
   1. 位置0，值为1，该情况下last=1
   2. 位置1，值为1，需要移动，count+=(last+1)-1=1，last=last+1=2
   3. 位置2，值为2，需要移动，count+=(last+1)-2=2，last=last+1=3
   4. 位置3，只为2，需要移动，count+=(last+1)-2=4，last=last+1=4
   5. 位置4，值为3，需要移动，count+=(last+1)-3=6，last=last+1=5
   6. 位置6，值为7>last，不需要移动
3. 因此总共需要移动6次。

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int size = A.size();
        sort(A.begin(),A.end());
        int last = INT_MIN;
        int count = 0;
        for(int i = 0;i<size;i++){
            if(A[i] > last){
                last = A[i];
            }else{
                count += ((last+1)-A[i]);
                last = last+1;
            }
        }
        return count;
    }
};

时间复杂度： O(NlogN)

解法二

分析：对数组进行计数，若每个数字出现的次数超过1，则把他多余的次数移给后序的数。这可能导致最大的数加1的格子中次数超过1，因此需要额外计算最后一个格子的状态。

1. 记数[1,1,2,2,3,4]，1:2,2:2,3:1,4:1
2. 遍历，1出现两次，因此需要移动2-1=1次，并把这一次加给2,因此2:3。
3. 2出现三次，需要移动2次，把这两次加给3，因此3:3。
4. 3出现三次，需要移动2次，把这两次加给4，因此4:3。
5. 4出现三次，需要移动2次，把这两次加给5，因此5:2。
6. 因为5是最后一个数了，因此直接计算即可，令d=2-1，(1+d)*d/2=1,需要移动1次。
7. 总共移动8次

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int count[40001]={0};
        int max = -1;
        for(auto a:A){
            if(a>max){
                max = a;
            }
            count[a]++;
        }
        int move = 0;
        for(int i = 0;i <=max;i++){
            if(count[i] > 1){
                int d = count[i]-1;
                move+=d;
                count[i+1]+=d;
            }
        }
        if(count[max+1] > 1){
            int d = count[max+1]-1;
            move+= (d+1)*d/2;
        }
        return move;
    }
};