945. 使数组唯一的最小增量
题目描述
输入一个整数数组 nums。
每次操作选一个下标 i，把 nums[i] 加 1。数只能增大，不能减小。
返回让数组中所有值两两不同所需的最少操作次数。测试数据保证答案能用 32 位整数表示。
示例 1
输入：nums = [1,2,2] 输出：1
解释：把其中一个 2 加 1 变成 3 即可。
示例 2
输入：nums = [3,2,1,2,1,7] 输出：6
解释：例如改成 [3,4,1,2,5,7]，共加 6 次，少于 6 次做不到。
数据范围
1 <= nums.length <= 10^50 <= nums[i] <= 10^5
解题思路：排序 + 贪心
排序后从小到大分配最终值。need 表示下一个数最小能取的值（前面已分配的最大值 + 1）。当前数 x 若小于 need，就只抬到 need，花费 need - x；否则保持不动。每个数都取“能取的最小值”，给后面的数留出最多空间，所以总增量最小。
为什么正确
处理完一个数后，已分配的值互不相同且都小于 need；moves 是它们的最小总增量。
复杂度分析
时间 O(n log n)，额外空间 O(1)（不计排序）。
易错点
只和前一个原始值比较。前一个数可能已经被抬高了，必须和它的新值（need）比较；另外 x 大于 need 时要把 need 跳到 x + 1，不能只加 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
nums.sort()
moves = need = 0
for x in nums:
moves += max(0, need - x)
need = max(need, x) + 1
return movesclass Solution {
public int minIncrementForUnique(int[] nums) {
Arrays.sort(nums);
int moves = 0, need = 0;
for (int x : nums) {
moves += Math.max(0, need - x);
need = Math.max(need, x) + 1;
}
return moves;
}
}class Solution {
public:
int minIncrementForUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
int moves = 0, need = 0;
for (int x : nums) {
moves += max(0, need - x);
need = max(need, x) + 1;
}
return moves;
}
};func minIncrementForUnique(nums []int) int {
sort.Ints(nums)
moves, need := 0, 0
for _, x := range nums {
moves += max(0, need-x)
need = max(need, x) + 1
}
return moves
}var minIncrementForUnique = function(nums) {
nums.sort((a, b) => a - b);
let moves = 0, need = 0;
for (const x of nums) {
moves += Math.max(0, need - x);
need = Math.max(need, x) + 1;
}
return moves;
};function minIncrementForUnique(nums: number[]): number {
nums.sort((a, b) => a - b);
let moves = 0, need = 0;
for (const x of nums) {
moves += Math.max(0, need - x);
need = Math.max(need, x) + 1;
}
return moves;
}其他解法
排序贪心与值域无关，适合一般情况；计数顺延在值域较小（本题 V ≤ 10^5）时线性完成，思路是把重复的数整体往后推。
解法 2：计数 + 顺延 时间 O(n + V)，空间 O(n + V)
用数组统计每个值出现的次数，V 是最大值。从小到大扫描每个值 v，若 cnt[v] > 1，多出来的 cnt[v] - 1 个数都必须至少加到 v + 1。把它们累加到 cnt[v + 1]，同时 moves 加上 cnt[v] - 1，因为每个数前进一步代价为 1。数组开到 V + n 足够容纳所有顺延。
不需要比较排序，值域不大时比排序更快。值域很大时数组开销大，此时排序更合适。
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
cnt = [0] * (max(nums) + len(nums) + 1)
for x in nums:
cnt[x] += 1
moves = 0
for v in range(len(cnt) - 1):
if cnt[v] > 1:
extra = cnt[v] - 1
moves += extra
cnt[v + 1] += extra
return movesclass Solution {
public int minIncrementForUnique(int[] nums) {
int mx = 0;
for (int x : nums) mx = Math.max(mx, x);
long[] cnt = new long[mx + nums.length + 1];
for (int x : nums) cnt[x]++;
long moves = 0;
for (int v = 0; v + 1 < cnt.length; v++) {
if (cnt[v] > 1) {
long extra = cnt[v] - 1;
moves += extra;
cnt[v + 1] += extra;
}
}
return (int) moves;
}
}class Solution {
public:
int minIncrementForUnique(vector<int>& nums) {
int mx = *max_element(nums.begin(), nums.end());
vector<long long> cnt(mx + nums.size() + 1, 0);
for (int x : nums) cnt[x]++;
long long moves = 0;
for (size_t v = 0; v + 1 < cnt.size(); v++) {
if (cnt[v] > 1) {
long long extra = cnt[v] - 1;
moves += extra;
cnt[v + 1] += extra;
}
}
return (int) moves;
}
};func minIncrementForUnique(nums []int) int {
mx := 0
for _, x := range nums {
mx = max(mx, x)
}
cnt := make([]int, mx+len(nums)+1)
for _, x := range nums {
cnt[x]++
}
moves := 0
for v := 0; v+1 < len(cnt); v++ {
if cnt[v] > 1 {
extra := cnt[v] - 1
moves += extra
cnt[v+1] += extra
}
}
return moves
}var minIncrementForUnique = function(nums) {
let mx = 0;
for (const x of nums) mx = Math.max(mx, x);
const cnt = new Array(mx + nums.length + 1).fill(0);
for (const x of nums) cnt[x]++;
let moves = 0;
for (let v = 0; v + 1 < cnt.length; v++) {
if (cnt[v] > 1) {
const extra = cnt[v] - 1;
moves += extra;
cnt[v + 1] += extra;
}
}
return moves;
};function minIncrementForUnique(nums: number[]): number {
let mx = 0;
for (const x of nums) mx = Math.max(mx, x);
const cnt: number[] = new Array(mx + nums.length + 1).fill(0);
for (const x of nums) cnt[x]++;
let moves = 0;
for (let v = 0; v + 1 < cnt.length; v++) {
if (cnt[v] > 1) {
const extra = cnt[v] - 1;
moves += extra;
cnt[v + 1] += extra;
}
}
return moves;
}