使数组唯一的最小增量
难度:
标签:
题目描述
代码结果
运行时间: 149 ms, 内存: 33.7 MB
/*
* 思路:
* 1. 首先对数组进行排序。
* 2. 然后使用Stream API遍历数组,从第二个元素开始,如果当前元素小于等于前一个元素,
* 则将当前元素增加到前一个元素加1,记录增加的次数。
* 3. 最后返回总共增加的次数。
*/
import java.util.Arrays;
public class Solution {
public int minIncrementForUnique(int[] nums) {
Arrays.sort(nums); // 对数组进行排序
int[] prev = {nums[0]}; // 记录前一个元素的值
int[] moves = {0}; // 记录操作次数
Arrays.stream(nums, 1, nums.length).forEach(num -> {
if (num <= prev[0]) { // 如果当前元素小于等于前一个元素
int increment = prev[0] + 1 - num; // 计算需要增加的量
moves[0] += increment; // 累加操作次数
prev[0] = num + increment; // 更新前一个元素的值
} else {
prev[0] = num; // 更新前一个元素的值
}
});
return moves[0]; // 返回总操作次数
}
}
解释
方法:
此题解采用了一个分步处理的策略:首先,通过遍历数组并使用一个集合来标记所有已经存在的数字,同时记录所有重复的数字到一个列表中。之后,对这个列表进行排序,然后对于列表中的每个数字,寻找一个尚未使用的最小数字使得该数字变得唯一。这通过逐渐增加一个目标数字并检查它是否被占用来实现。每次找到一个合适的数字后,计算增加的步数,并将此目标数字标记为已使用。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中提到的集合用于存储每个独特的数字,为什么不直接在数组内部操作而选择使用额外的数据结构?
▷🦆
你是如何确定重复数字列表`f`的初始值应该设置为`x + 1`,而不是其他值?
▷🦆
为什么在处理重复数字时,选择对它们进行排序?这种排序对算法的性能优化有什么具体影响?
▷🦆
在解决方案中,每次找到一个未使用的数字后,都会进行`target += 1`的操作直到找到可用位置,这种方法在最坏情况下的性能如何?
▷