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

https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200323203056524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hobXk3Nw==,size_16,color_FFFFFF,t_70

哇昨天做这题真的心态崩了，暴力都不会暴力 ????
其实暴力解法第一次做的时候在纸上已经推算出来了
例如1,1,1,2,4,5这种情况
1,1,1,2,4,5，每个重复的数字，只保留一个，然后其余的都往后加就行了
1,2,2,2,4,5
1,2,3,3,4,5
1,2,3,4,4,5
1,2,3,4,5,5
1,2,3,4,5,6
一共需要7次
于是我按照这个思路尝试了第一次，注意要先排序保证有序

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        size=len(A)
        dct=dict()
        for num in A:
            dct[num]=dct.get(num,0)+1
        ans=0
        while len(dct)!=size:
            for k,v in dct.items():
                if v!=1:
                    fk,fv=k,v
                    break
            cnt=fv-1
            dct[fk]=1
            dct[fv+1]=dct.get(fv+1,0)+cnt
            ans+=cnt
        return ans

超 时 大 成 功

第二次尝试
看到第一次尝试超时了，丝毫没有意识到是寻找第一个重复数的操作耗时太多，反而想了个更超时的操作 ????
用一个足够大的空数组，填满数字
对每个重复的数字，计算它与下一个0的距离，然后标记下一个0的值为1
重复以上行为，直到start与size相等
这个操作看起来很美好啊
对于1,1,1,2,4,6,9
重复的两个1，直接填到空缺的3和5中，并且距离也很好算，一个是3-1，一个是5-1，一下子就得出移动次数了
变成1,2,3,4,5,6,9
但是这个寻找下一个0的操作实在是耗时太长了。。。

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        size=len(A)
        ans=0
        dct=[0]*80000  #存放数字的映射
        start=0 #初始数字长度
        lst=[]  #存放那些有重复的数字
        for num in A:
            if dct[num]==0:
                start+=1
            dct[num]+=1
            if dct[num]==2: #标记有重复的元素，并且只标记一次
                lst.append(num)
        lst.sort()        
        ind=0
        zero=dct.index(0)   #第一个不为0下标
        while start!=size:
            # 统计有多少个重复数，只保留一个，移动其它的重复数
            t=dct[lst[ind]]-1
            for i in range(t):
                while zero<lst[ind] or dct[zero]!=0:   #只往后寻找0 *这一步太耗时了*
                    zero=zero+1+dct[zero+1:].index(0)
                ans+=zero-lst[ind]
                dct[zero]=1
            ind+=1
            start+=t
        return ans

又一次超时大成功
这里解释下为什么dct的大小为80000，因为最差的情况就是40000个40000，往后移动刚好填满40000~79999

看了一下别人的暴力，真的完爆我了

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        dct=[0]*800001
        ans=0
        for num in A:
            dct[num]+=1
        for i in range(len(dct)):
            if dct[i]>1:
                ans+=dct[i]-1
                dct[i+1]+=dct[i]-1
        return ans

多么朴素的解法啊，只需要一个排序，然后从前往后的遍历，碰到重复的就往后移动，跟我纸上推出来的规律是一样的，不过我的解法超时了
其余的解法我也不会了，，看下别人的题解吧

官方题解

我第二次的尝试和这个方法一很像啊…不过我是每次碰到重复元素都找一次0…超时了

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

重点是怎么找到这些没出现过的2,4,6

噢。。可以在读数据的时候就进行移动操作啊…????
尝试着自己重新写了一下

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        dct=[0]*80001
        lst=[]	#存放重复数
        for num in A:
            dct[num]+=1
        ans=0
        for i in range(len(dct)):
            if dct[i]>1:
                lst.append(i)
            elif dct[i]==0: #找到一个0
                if lst==[]:	#没有重复数则跳过
                    continue
                num=lst[0]	#取出最小的重复数
                dct[lst[0]]-=1
                ans+=i-lst[0]
                if dct[lst[0]]==1:	#移动lst
                    lst=lst[1:]
        return ans

通过了
照着优化又改进了一下，优化先减再加的原因就是ans总是等于新的0的下标-旧的重复的下标，那么先减再加完全没有问题

不用存重复的数字了，很方便，但是我们还要存目前有多少个数字重复了，这样在遇到0的时候再加上

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        dct=[0]*80001
        ans=0
        cnt=0	#记录有多少个重复数字
        for num in A:
            dct[num]+=1
        for i in range(len(dct)):
            if dct[i]>1:
                ans-=(dct[i]-1)*i	#先减
                cnt-=(dct[i]-1)		#记录重复数字
            elif dct[i]==0:
                if cnt==0:	#当前并没有重复数字
                    continue
                ans+=i
                cnt+=1
        return ans

更快了

方法二 排序

这个解法很妙啊，特别是这一点

如果 A[i - 1] < A[i]，则区间 \big[A[i - 1] + 1, A[i] - 1\big][A[i−1]+1,A[i]−1] 里的数都是没有出现过的

那每次碰到一个空的区间，就可以把之前重复的数填进来了
尝试着自己写一下