Leetcode 945 Minimum Increment to Make Array Unique

发表于 |

给定一个数组A，你可以进行一次操作使得A中的任意一个数加一
为了使A中的每个元素都不同，问最少需要进行多少次操作。

Example 1:
Input: [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].

Example 2:
Input: [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

Note:

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

思路分析：
首先我们从简单的情况开始考虑，例如 A = [0,0,1,1]
经过若干次操作，我们知道最后的序列为 B = [0,1,2,3]
那么操作次数 m = (0+1+2+3) - sum(A)

接下来考虑， A = [0,0,1,1,4]
最后的序列为 B = [0,1,2,3,4]
我们发现最后一个4其实没影响到结果，因为之前序列的结尾3小于4
我们现在把上一个序列结尾的数定义成end，例如对于序列[0,0,1,1]，end = 3
所以我们发现，一旦有：
end < A[i]， 我们就可以计算出A[:i]这段序列的操作次数
以此类推，可以得出最后的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def minIncrementForUnique(self, A):
        A.append(float('inf'))
        A.sort()
        n = len(A)
        res = 0
        start = end = s = A[0]
        for i in range(1, n):
            if end < A[i]:
                res += (end+start)*(end-start+1)//2 - s
                start = end = s = A[i]
            else:
                end += 1
                s += A[i]
        return res