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

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

给定整数数组 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 操作是不能让数组的每个值唯一的。

提示：

1. $0 <= A.length <= 40000$
2. $0 <= A[i] < 40000$

一、排序O(nlogn)

二、计数排序O(N)

三、线性探测法O(N) （含路径压缩）

一、排序O(nlogn)

逻辑：先排序，再依次遍历数组元素，若当前元素小于等于它前一个元素，则将其变为前一个数+1。

class Solution {
    public int minIncrementForUnique(int[] A) {
        Arrays.sort(A);
        int cnt=0;
        for(int i=1;i<A.length;i++){
            if(A[i]<=A[i-1]){
                int pre=A[i];
                A[i]=A[i-1]+1;
                cnt+=A[i]-pre;
            }
        }
        return cnt;
    }
}

复杂度分析

• 时间复杂度：$O(N\log N)$，其中 N 是数组 A 的长度，即排序的时间复杂度。
• 空间复杂度：$O(\log N)$，排序需要额外 $O(\log N)$ 的栈空间。

二、计数排序O(N)

计数思想的稍微优化

当我们找到一个没有出现过的数的时候，将之前某个重复出现的数增加成这个没有出现过的数。注意，这里 「之前某个重复出现的数」 是可以任意选择的，它并不会影响最终的答案，因为将 P 增加到 X 并且将 Q 增加到 Y，与将 P 增加到 Y 并且将 Q 增加到 X 都需要进行 (X + Y) - (P + Q) 次操作。

例如当数组 A 为 [1, 1, 1, 1, 3, 5] 时，我们发现有 3 个重复的 1，且没有出现过 2，4 和 6，因此一共需要进行 (2 + 4 + 6) - (1 + 1 + 1) = 9 次操作。

算法

首先统计出每个数出现的次数，然后从小到大遍历每个数 x：

• 如果 x 出现了两次以上，就将额外出现的数记录下来（例如保存到一个列表中）；
• 如果 x 没有出现过，那么在记录下来的数中选取一个 v，将它增加到 x，需要进行的操作次数为 x - v。

在这里可以进行优化，例如输入 [3, 2, 1, 2, 1, 7]，计数之后有两个 1 和两个 2。我们先看最小的数，两个 1 重复了，需要有一个增加到 2，这样 2 的数量变成了三个。在三个 2 中，又有两个需要增加到 3，然后又出现了两个 3…… 以此类推，可以计算出需要增加的次数。和官方给出的题解来说，复杂度由$O(n+80000)$变为$O(n+40000)$

class Solution {
    public int minIncrementForUnique(int[] A) {
        int[] cnt=new int[40001];
        int max=-1,ans=0;
        for(int i=0;i<A.length;i++){
            cnt[A[i]]++;
            max=Math.max(max,A[i]);
        }
        for(int i=0;i<=max;i++){
            if(cnt[i]>1){
                int t=cnt[i]-1;
                cnt[i+1]+=t;
                ans+=t;
            }
        }
        int t=cnt[max+1]-1;
        ans+=(t+1)*t/2;  // 1+2+3+4+...+t 每次移动累加的步数
        return ans;
    }
}

// 最后, counter[max+1]里可能会有从counter[max]后移过来的，counter[max+1]里只留下1个，其它的d个后移。
// 设 max+1 = x，那么后面的d个数就是[x+1,x+2,x+3,...,x+d],
// 因此操作次数是[1,2,3,...,d],用求和公式求和。

• 时间复杂度：设 n 为数组元素的个数，k 为数组元素的可能取值个数（本期中 k = 40000），这个算法的时间复杂度是 O(n + k)。

三、线性探测法O(N) （含路径压缩）

这道题换句话说，就是需要把原数组映射到一个地址不冲突的区域，映射后的地址不小于原数组对应的元素。
比如[3, 2, 1, 2, 1, 7]就映射成了[3, 2, 1, 4, 5, 7]。

我想了下，这道题目其实和解决hash冲突的线性探测法比较相似！
如果地址冲突了，会探测它的下一个位置，如果下一个位置还是冲突，继续向后看，直到第一个不冲突的位置为止。

关键点：因为直接线性探测可能会由于冲突导致反复探测耗时太长，因此我们可以考虑探测的过程中进行路径压缩。
怎么路径压缩呢？就是经过某条路径最终探测到一个空位置x后，将这条路径上的值都变成空位置所在的下标x，那么假如下次探测的点又是这条路径上的点，则可以直接跳转到这次探测到的空位置x，从x开始继续探测。

下面用样例2：[3, 2, 1, 2, 1, 7]，来模拟一遍线性探测的过程.

step1: 插入3：

因为3的位置是空的，所以直接放入3即可。（此时数组变成了上图，红色表示本次的更改）

step2: 插入2：

因为2的位置是空的，所以直接放入2即可。（此时数组变成了上图，红色表示本次的更改）

step3: 插入1：

因为1的位置是空的，所以直接放入1即可。（此时数组变成了上图，红色表示本次的更改）

step4: 插入2：

此时我们发现2的位置已经有值了，于是继续向后探测，直到找到空位4，于是2映射到了4。
并且！！我们要对刚刚走过的路径2->3->4进行压缩，即将他们的值都设置为本次探测到的空位4(那么下次探测就可以直接从4往后找了)。
（此时数组变成了上图，红色表示本次的更改）

step5: 插入1：

此时我们发现1的位置已经有值了，于是向后探测，探测到了2，发现2的位置也有值了，但是由于2在上次的过程中存了上次的空位4，所以我们直接跳转到4+1即从5开始探测就行了（而不需要重复走一遍2->3->4这条路径喽！），此时我们发现5是个空位，因此将1映射到5，并且对与刚刚走过的路径1->2->5进行路径压缩即使其都映射到5！
（此时数组变成了上图，红色表示本次的更改）

step6: 插入7：

因为7的位置是空的，所以直接放入7即可。（此时数组变成了上图，红色表示本次的更改）

class Solution {
    public int[] pos=new int[80000];
    public int minIncrementForUnique(int[] A) {
        Arrays.fill(pos,-1);  // -1表示空位
        int ans=0;
        for(int a:A){
            int b=findPos(a);
            ans+=b-a;
        }
        return ans;
    }
    // 线性探测法寻址（含路径压缩）
    public int findPos(int a){
        int b=pos[a];
        // 如果对应的位置是空位，直接放入
        if(b==-1){
            pos[a]=a;
            return a;
        }
        // 否则向后寻址
        // 直到找到一个空位，同时更新一路上的路径
        b=findPos(b+1);
        pos[a]=b;  // 寻址后的新空位要重新赋值给pos[a]哦，路径压缩就是体现在这里。
        return b;
    }
}