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

源代码 · 2024-9-25 12:59:07

标题：

给你一个整数数组 nums 。每次 move 使用将会选择恣意一个满足 0 <= i < nums.length 的下标 i，并将 nums 递增 1。
返回使 nums 中的每个值都酿成唯一的所必要的最少使用次数。
示例 1：
输入：nums = [1,2,2]
输出：1
解释：颠末一次 move 使用，数组将变为 [1, 2, 3]。
示例 2：
输入：nums = [3,2,1,2,1,7]
输出：6
解释：颠末 6 次 move 使用，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 使用是不能让数组的每个值唯一的。
提示：
1 <= nums.length <= 10^5
0 <= nums <= 10^5
思绪：

java代码：

class Solution { public int minIncrementForUnique(int[] nums) { Arrays.sort(nums); int ans = 0, taken = 0; for (int i = 1; i < nums.length; ++i) { if (nums[i - 1] == nums) { taken++; ans -= nums; } else { int give = Math.min(taken, nums - nums[i - 1] - 1); ans += give * (give + 1) / 2 + give * nums[i - 1]; taken -= give; } } if (nums.length > 0) { ans += taken * (taken + 1) / 2 + taken * nums[nums.length - 1]; } return ans; }}

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

所属分类: 问答交流

新帖推荐: 30日

推荐作品