「沙茶敏碎碎念」一天一个LeetCode中等题目（3月22）给定整数数组A

给定整数数组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<=400000<=A[i]<40000来源：力扣（LeetCode）解法一【「沙茶敏碎碎念」一天一个LeetCode中等题目（3月22）】这个题目，数据范围才4万，其实我们可以暴力模拟，先统计每一个数字总共有多少个数。例如数组[1,2,2]可以表示为,B[1]=1,B[2]=2 。表示1出现了1次， 2出现了2次，那么接下来我们有什么用呢？因为每个数字只能出现1次，剩下的只能+1了，所以，假如我们初始的数字是[3,3,3],那么B[3]=3,我们自己用一个3 ，剩下的进行加一，也就是B[4]=2 ，结果为2 ，然后接下来检查到B[4]>1 ，又把一个加到B[5] 。这样子我们只要简单的遍历即可，算法复杂度为O（N）。
解法二第二个解法，是贪心原则。我们先了解了解下下面这种情况， [2,2,3],第2个数字加2跟第2 ， 3个数字分别加1其实是一样的。又因为我们只有一种操作，也就是+1 ，基于这样，我们可以从小到大处理每一个数。我们先进行一次快排，然后然后从左到右，依次处理每一个数，每次都将它处理到比上一个数大。这样我们需要依次O（NlogN）的排序，跟O（N）的扫描，综合算法复杂度为O（NlogN）。下面是解法二的代码

文章图片