「LeetCode每日一题」——945. 使数组唯一的最小增量
945. 使数组唯一的最小增量
链接：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/
难度：中等
题目
给定整数数组 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
思路
这道题我们可以先排序，再把他们变得不相同。
比如：[3,2,1,2,1,7] 排序后变成 [1,1,2,2,3,7]
然后遍历对比前后两个数字，把他们变成递增的，这样就得到了最小的增量。
代码见解决方案。
方案代码
解决方案：
class Solution:
def minIncrementForUnique(self, A: List[int]) -> int:
A.sort()
l = len(A)
res = 0
for i in range(l-1):
if A[i] >= A[i+1]:
res += A[i]-A[i+1]+1
A[i+1] += A[i]-A[i+1]+1
return res
原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/247.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」—— 912. 排序数组
912. 排序数组 链接：https://leetcode-cn.com/problems/sort-an-array/难度：中等 题目 给你一个整数数组 nums，请你…
-
「LeetCode每日一题」—— 460. LFU缓存
460. LFU缓存 题目链接：https://leetcode-cn.com/problems/lfu-cache/难度：困难 题目 点击原文链接跳转查看题目 请你为 最不经常使…
-
「LeetCode每日一题」——1160. 拼写单词
1160. 拼写单词 链接：https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters…
-
「LeetCode每日一题」—— 11. 盛最多水的容器
11. 盛最多水的容器 链接：https://leetcode-cn.com/problems/container-with-most-water/难度：中等 题目 思路 这道题和…
-
「LeetCode每日一题」—— 72. 编辑距离
72. 编辑距离 题目链接：https://leetcode-cn.com/problems/edit-distance/难度：困难 题目 给你两个单词 word1 和&…
-
「LeetCode每日一题」——322. 零钱兑换
322. 零钱兑换 链接：https://leetcode-cn.com/problems/coin-change/难度：中等 题目 给定不同面额的硬币 coins 和一个总金额 …
-
「LeetCode每日一题」——LCCI.17.16. 按摩师
LCCI.17.16. 按摩师 链接：https://leetcode-cn.com/problems/the-masseuse-lcci/难度：简单 题目 一个有名的按摩师会收到…
-
「LeetCode每日一题」——914. 卡牌分组
914. 卡牌分组 链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/难度：简单 题目 给定一副…
-
「LeetCode每日一题」——836. 矩形重叠
836. 矩形重叠 链接：https://leetcode-cn.com/problems/rectangle-overlap/难度：简单 题目 矩形以列表 [x1, y1, x2…
-
「LeetCode每日一题」——876. 链表的中间结点
876. 链表的中间结点 链接：https://leetcode-cn.com/problems/middle-of-the-linked-list/难度：简单 题目 给定一个带有…
您必须登录才能发表评论。