945. Minimum Increment to Make Array Unique

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

这道题给了一个数组,说是每次可以将其中一个数字增加1,问最少增加多少次可以使得数组中没有重复数字。给的两个例子可以帮助我们很好的理解题意,这里主要参考了 lee215 大神的帖子,假如数组中没有重复数字的话,则不需要增加,只有当重复数字存在的时候才需要增加。比如例子1中,有两个2,需要将其中一个2增加到3,才能各不相同。但有时候只增加一次可能并不能解决问题,比如例子2中,假如要处理两个1,增加其中一个到2并不能解决问题,因此2也是有重复的,甚至增加到3还是有重复,所以一直得增加到4才行,但此时如何知道后面是否还有1,所以需要一个统一的方法来增加,最好是能从小到大处理数据,则先给数组排个序,然后用一个变量 need 表示此时需要增加到的数字,初始化为0,由于是从小到大处理,这个 need 会一直变大,而且任何小于 need 的数要么是数组中的数,要么是某个数字增后的数,反正都是出现过了。然后开始遍历数组,对于遍历到的数字 num,假如 need 大于 num,说明此时的 num 是重复数字,必须要提高到 need,则将 need-num 加入结果 res 中,反之若 need 小于 num,说明 num 并未出现过,不用增加。然后此时更新 need 为其和 num 之间的较大值并加1,因为 need 不能有重复,所以要加1,参见代码如下:

解法一:

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int res = 0, need = 0;
        sort(A.begin(), A.end());
        for (int num : A) {
            res += max(need - num, 0);
            need = max(num, need) + 1;
        }
        return res;
    }
};

假如数组中有大量的重复数字的话,那么上面的方法还是需要一个一个的来处理,来看一种能同时处理大量的重复数字的方法。这里使用了一个 TreeMap 来统计每个数字和其出现的次数之间的映射。由于 TreeMap 可以对 key 自动排序,所以就没有必要对原数组进行排序了,这里还是要用变量 need,整体思路和上面的解法很类似。建立好了 TreeMap 后开始遍历,此时单个数字的增长还是 max(need - num, 0),这个已经在上面解释过了,由于可能由多个,所以还是要乘以个数 a.second,到这里还没有结束,因为 a.second 这多么多个数字都被增加到了同一个数字,而这些数字应该彼此再分开,好在现在没有比它们更大的数字,那么问题就变成了将k个相同的数字变为不同,最少的增加次数,答案是 k*(k-1)/2,这里就不详细推导了,其实就是个等差数列求和,这样就可以知道将 a.second 个数字变为不同总共需要增加的次数,下面更新 need,在 max(need, num) 的基础上,还要增加个数 a.second,从而到达一个最小的新数字,参见代码如下:

解法二:

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int res = 0, need = 0;
        map<int, int> numCnt;
        for (int num : A) ++numCnt[num];
        for (auto &a : numCnt) {
            res += a.second * max(need - a.first, 0) + a.second * (a.second - 1) / 2;
            need = max(need, a.first) + a.second;
        }
        return res;
    }
};

再来看一种联合查找 Union Find 的方法,这是一种并查集的方法,在岛屿群组类的问题上很常见,可以搜搜博主之前关于岛屿类题目的讲解,很多都使用了这种方法。但是这道题乍一看好像跟群组并没有明显的关系,但其实是有些很微妙的联系的。这里的 root 使用一个 HashMap,而不是用数组,因为数字不一定是连续的,而且可能跨度很大,使用 HashMap 会更加省空间一些。遍历原数组,对于每个遍历到的数字 num,调用 find 函数,这里实际上就是查找上面的方法中的 need,即最小的那个不重复的新数字,而 find 函数中会不停的更新 root[x],而只要x存在,则不停的自增1,直到不存在时候,则返回其本身,那么实际上从 num 到 need 中所有的数字的 root 值都标记成了 need,就跟它们是属于一个群组一样,这样做的好处在以后的查询过程中可以更快的找到 need 值,这也是为啥这种方法不用给数组排序的原因,若还是不理解的童鞋可以将例子2代入算法一步一步执行,看每一步的 root 数组的值是多少,应该不难理解,参见代码如下:

解法三:

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int res = 0;
        unordered_map<int, int> root;
        for (int num : A) {
            res += find(root, num) - num;
        }
        return res;
    }
    int find(unordered_map<int, int>& root, int x) {
        return root[x] = root.count(x) ? find(root, root[x] + 1) : x;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/945

参考资料:

https://leetcode.com/problems/minimum-increment-to-make-array-unique/

https://leetcode.com/problems/minimum-increment-to-make-array-unique/discuss/197687/JavaC%2B%2BPython-Straight-Forward

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation