# 945. Minimum Increment to Make Array Unique 使数组唯一的最小增量

@TOC

## # 题目描述

Given an array of integers A, a move consists of choosing any `A[i]`, and incrementing it by `1`.

Return the least number of moves to make every value in `A` unique.

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

## # 解题方法

### # 暴力求解，TLE

``````class Solution(object):
def minIncrementForUnique(self, A):
"""
:type A: List[int]
:rtype: int
"""
N = len(A)
seats = [0] * 80010
res = 0
for a in A:
if not seats[a]:
seats[a] = 1
else:
pos = a
while pos < 80010 and seats[pos] == 1:
pos += 1
seats[pos] = 1
res += pos - a
return res
``````

### # 一次遍历

``````class Solution(object):
def minIncrementForUnique(self, A):
"""
:type A: List[int]
:rtype: int
"""
N = len(A)
if N == 0: return 0
A.sort()
res = 0
prev = A[0]
for i in range(1, N):
if A[i] <= prev:
prev += 1
res += prev - A[i]
else:
prev = A[i]
return res
``````

## # 日期

2018 年 11 月 24 日 —— 周日开始！一周就过去了～