前言
考试陆陆续续结束,长沙最热的一段时间叶快到了。不过没啥大不了的,冲!冲一个好的未来出来。而且暑假还有美好生活体验版,累是不可能累的。还有希望宝宝的颈椎听听话话的!
题目
给定整数数组 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 操作是不能让数组的每个值唯一的。
提示:
- 0 <= A.length <= 40000
- 0 <= A[i] < 40000
思路
这道题一开始是打算最求一种速度最快而且不需要太多内存消耗的解法,就在排序的同时进行判断以及move操作。可是后来发现,数组在乱序的时候move操作无法判断它递增后的值是否存在,所以最终的结果会导致繁琐而且效率没有很大的提高。就选择下面这种先排序后move的方法。只需让A[i-1] 与 A[i] 相比判断大小,而move的次数就是两者之差加1.如下图:
代码
def minIncrementForUnique(A) :
A.sort()
count = 0 #记录move的次数
for i in range(1,len(A)):
if A[i] <= A[i-1] :
count += ( A[i-1] - A[i] + 1)
A[i] = A[i-1] + 1
return count