945、使数组唯一的最小增量
给定整数数组 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
链接：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique
题解
1、暴力
class Solution {
public int minIncrementForUnique(int[] A) {
Set<Integer> set = new HashSet<>();
int moveTimes = 0;
for (int i = 0;i < A.length;i++) {
// 要做到 O(1) 或者 O(logn)
while (set.contains(A[i])) {
A[i]++;
moveTimes++;
}
set.add(A[i]);
}
return moveTimes;
}
}
2、计数法
- 统计重复出现的次数，初始值是0（表示没有出现过）
class Solution {
public int minIncrementForUnique(int[] A) {
int[] count = new int[80000]；// 初始值为0
// 统计出现的次数
for (int x : A) {
count[x]++;
}
int ans = 0; // 需要递增的次数
int token = 0; // 统计重复硬币的个数
for (int x = 0;x < 80000;x++) {
// x出现了多次
if (count[x] >= 2) {
token += count[x] - 1; // 重复的字数增加
ans -= x * (count[x] - 1); // 重复的数字数值统计
} else if(token > 0 && count[x] == 0) { // 有重复的数字没有操作，当前数字x没有出现过
token--; // 减少一个重复的数字
ans += x; // 等价于 x - y * (count[x] - 1)
}
}
return ans;
}
}
class Solution {
public int minIncrementForUnique(int[] A) {
// counter数组统计每个数字的个数。
//（这里为了防止下面遍历counter的时候每次都走到40000，所以设置了一个max，这个数据量不设也行，再额外设置min也行）
int[] counter = new int[40001];
int max = -1;
for (int num: A) {
counter[num]++;
max = Math.max(max, num);
}
// 遍历counter数组，若当前数字的个数cnt大于1个，则只留下1个，其他的cnt-1个后移
int move = 0;
for (int num = 0; num <= max; num++) {
if (counter[num] > 1) {
int d = counter[num] - 1;
move += d;
counter[num + 1] += d;
}
}
// 最后, counter[max+1]里可能会有从counter[max]后移过来的，counter[max+1]里只留下1个，其它的d个后移。
// 设 max+1 = x，那么后面的d个数就是[x+1,x+2,x+3,...,x+d],
// 因此操作次数是[1,2,3,...,d],用求和公式求和。
int d = counter[max + 1] - 1;
move += (1 + d) * d / 2;
return move;
}
}
// 作者：sweetiee
// 链接：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/solution/ji-shu-onxian-xing-tan-ce-fa-onpai-xu-onlogn-yi-ya/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
3、排序法
先排序，这样重复的数字就排在了一起
class Solution {
public int minIncrementForUnique(int[] A) {
// 排序
Arrays.sort(A);
int ans = 0,taken = 0;
// 计算需要操作的次数
for (int i = 1;i < A.length;i++) {
if (A[i-1] == A[i]) {// 出现重复数字
taken++;
ans -= A[i];// 基础值
} else { //
// 获取最多可以改变的个数
int give = Math.min(taken,A[i] - A[i-1] - 1);
// 减去操作数
ans += give * (give + 1)/2 + give * A[i - 1];
// 减去已操作的个数
taken -= give;
}
}
// 处理最后一个数
if (A.length > 1) {
ans += taken * (taken + 1)/2 + taken * A[A.length - 1];
}
return ans;
}
}
4、将前面的数字累加到下一个数
class Solution {
public int minIncrementForUnique(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
int[] status = new int[50000];
int counts = 0;
for(int num : nums) {
status[num]++;// num数量+1
}
for(int i = 0; i < 50000; i++) {
if(status[i] > 1) {
int expect = status[i] - 1;
counts += expect;
status[i + 1] += expect;// 下一个数累加
status[i] = 1;
}
}
return counts;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
