难度：★★★☆☆
类型：数组
方法：排序

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定整数数组 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

解答

这道题不难，但是体现了排序的强大作用。

我们先将A数组升序排序，然后从小大两两遍历，一旦遇到左边A[i-1]元素大于等于右边元素A[i]的情况，则需要将右边元素进行加一操作，直到稍微超过左边元素为止（也就是A[i]=A[i-1]+1）。及时将位移的步数记录在结果ans中。

这里有必要说明一下，为什么不能只考虑等于号成立，而需要考虑大于等于号成立。因为在遍历的过程中，难免遇到超过2个元素都一样的情况，例如[1,1,1]，这时如果第二个1变成了2，[1,2,1]，那么第三个元素肯定是要变的，而且要超过2才对，变成[1,2,3]。因此判别条件不是等于号，而是大于等于号。

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

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析