945.使数组唯一的最小增量

使数组唯一的最小增量

给你一个整数数组 nums。每次 move 操作将会选择任意满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。

返回使 nums 中的每个值都变成唯一的所需要的最少操作数。

示例 1:

输入：nums = [1,2,2]
输出：1

示例 2:

输入：nums = [3,2,1,2,1,7]
输出：6

提示:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

解析

先排序，然后遍历数组，确保每个元素比前一个元素大，记录需要增加的次数。

var minIncrementForUnique = function (nums) {
  nums.sort((a, b) => a - b);
  let moves = 0;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] <= nums[i - 1]) {
      moves += nums[i - 1] - nums[i] + 1;
      nums[i] = nums[i - 1] + 1;
    }
  }

  return moves;
};

时间复杂度 O(n log n)，空间复杂度 O(1)。