945. 使数组唯一的最小增量，贪心 O(max(A_i))

22 Mar 2020

预计阅读时间 ~2 分钟

解题思路

观察可发现，此题的A[i]范围极小（0 <= A[i] < 40000），所以可以用一个Hash记录数组里每个元素出现的次数，如果有重复的元素，那么就是需要处理的。

由于只能进行递增操作，需要使每个元素增加的次数最小，那么就让它增加为最近的不重复元素即可。比如 [1, 2, 2, 2, 3, 3]，在hash里为[0, 1, 3, 2]（0出现0次，1出现1次，2出现3次，3出现2次），

发现2不唯一，就需要把多余的2变为与它相邻的元素3， hash=[0, 1, 1, 5]，minInc = 2；
发现3不唯一，就需要把多余的3变为与它相邻的元素4， hash=[0, 1, 1, 1, 4]， minInc = 2 + 4 = 6；
以此类推，直到hash的边界max(A[i])，假设hash[max(A[i])] - 1 = n，用求和公式算出边界答案, $minInc = minInc + \frac{n(n+1)}{2}$ 。因为只需要把多余的元素依次变为 $max(A[i])+1, max(A[i])+2, ..., + max(A[i]) + n$

复杂度分析：

时间复杂度: $O(max(A_{i}))$
空间复杂度: $O(max(A_{i}))$

代码

class Solution {
    public int minIncrementForUnique(int[] A) {
        int[] times = new int[40001];
        int maxValue = 0;
        for (int a: A) {
            times[a] ++;
            if (a > maxValue) maxValue = a;
        }
        int minInc = 0;
        for (int i = 0; i <= maxValue; ++i) {
            if (times[i] > 0) {
                times[i+1] += times[i]-1;
                minInc += times[i]-1;
            }
        }
        if (times[maxValue+1] > 0) {
            int n = times[maxValue+1] - 1;
            minInc += n*(n+1)/2;
        }
        return minInc;
    }
}

leetcode 中等