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

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

解法一：
先记录每个数字出现的次数，和max，min；然后按照从小到大的顺序将每个数字铺开，比如[2,2,2,2,2] 铺开成[2,3,4,5,6]，前提是之前的铺开的数的最大值preMax小于2，否则依旧会有重叠部分，此时将铺开的部分再整体平移，平移的位数即重叠的位数; 铺开后更新最大值preMax

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        # count = collections.Counter(A)
        # minNum, maxNum = min(A), max(A)
        count = {}
        minNum, maxNum = 0, 0
        for a in A:
            count[a] = count.get(a, 0) + 1
            minNum = min(minNum, a)
            maxNum = max(maxNum, a)
        res, preMax = 0, -1
        for num in range(minNum, maxNum+1):
            if num in count:
                times = count[num]
                if num > preMax:
                    res += times * (times - 1) // 2
                    preMax = num + times - 1
                else:
                    res += (preMax - num + 1) * times + times * (times - 1) // 2 
                    preMax += times
        return res

解法二：
排序，

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        preMax, res = -1, 0
        for a in A:
            if a > preMax:
                preMax = a
            else: 
                res += preMax - a + 1
                preMax += 1
        return res