class Solution {
public:
int minIncrementForUnique(vector<int>& nums) {
}
};
945. 使数组唯一的最小增量
给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 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 <= 1050 <= nums[i] <= 105原站题解
php 解法, 执行用时: 612 ms, 内存消耗: 39.6 MB, 提交时间: 2023-09-20 11:28:06
class Solution {
/**
* @param Integer[] $A
* @return Integer
*/
function minIncrementForUnique($A) {
// 先排序在比较
$a = self::quickSort($A);
$count = count($a);
$last = $a[0];
$sum = 0;
for($i = 1; $i < $count; $i++){
if($a[$i] <= $last){
$sum += $last + 1 - $a[$i];
$last += 1;
} else {
$last = $a[$i];
}
}
return $sum;
}
function quickSort($A) {
$count = count($A);
if($count < 2){
return $A;
}
$mid = $A[0];
$left = []; $right = [];
foreach($A as $k => $value){
if($k == 0){
continue;
}
if($value > $mid){
$right[] = $value;
} else {
$left[] = $value;
}
}
return array_merge(self::quickSort($left), [$mid], self::quickSort($right));
}
}
golang 解法, 执行用时: 232 ms, 内存消耗: 8.4 MB, 提交时间: 2023-09-20 11:27:20
func minIncrementForUnique(A []int) int {
if len(A) == 0 {
return 0
}
sort.Ints(A)
res, value := 0, A[0]
for i:=1; i<len(A); i++ {
if A[i] <= value {
value++
res += value - A[i]
} else {
value = A[i]
}
}
return res
}
rust 解法, 执行用时: 56 ms, 内存消耗: 4.5 MB, 提交时间: 2023-09-20 11:27:05
use std::collections::HashMap;
impl Solution {
pub fn min_increment_for_unique(nums: Vec<i32>) -> i32 {
let (mut max, mut ans) = (0, 0);
let mut map = HashMap::new();
for n in nums {
*map.entry(n).or_insert(0) += 1;
max = max.max(n);
}
for n in 0..=max {
if let Some(&cnt) = map.get(&n) {
if cnt > 1 {
*map.entry(n + 1).or_insert(0) += cnt - 1;
ans += cnt - 1;
}
}
}
if let Some(&cnt) = map.get(&(max + 1)) {
ans += cnt * (cnt - 1) / 2;
}
ans
}
}
cpp 解法, 执行用时: 168 ms, 内存消耗: 64.4 MB, 提交时间: 2023-09-20 11:26:24
class Solution {
public:
int minIncrementForUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0, taken = 0;
for (int i = 1; i < (int)nums.size(); ++i) {
if (nums[i - 1] == nums[i]) {
taken++;
ans -= nums[i];
} else {
int give = min(taken, nums[i] - nums[i - 1] - 1);
ans += give * (give + 1) / 2 + give * nums[i - 1];
taken -= give;
}
}
if (nums.size() > 0) {
ans += taken * (taken + 1) / 2 + taken * nums.back();
}
return ans;
}
};
python3 解法, 执行用时: 364 ms, 内存消耗: 26.9 MB, 提交时间: 2023-09-20 11:25:54
class Solution:
# 计数
def minIncrementForUnique1(self, nums: List[int]) -> int:
count = [0] * 200000
for x in nums:
count[x] += 1
ans = taken = 0
for x in range(200000):
if count[x] >= 2:
taken += count[x] - 1
ans -= x * (count[x] - 1)
elif taken > 0 and count[x] == 0:
taken -= 1
ans += x
return ans
# 排序
def minIncrementForUnique(self, nums: List[int]) -> int:
nums.sort()
nums.append(200000)
ans = taken = 0
for i in range(1, len(nums)):
if nums[i - 1] == nums[i]:
taken += 1
ans -= nums[i]
else:
give = min(taken, nums[i] - nums[i - 1] - 1)
ans += give * (give + 1) // 2 + give * nums[i - 1]
taken -= give
return ans
java 解法, 执行用时: 21 ms, 内存消耗: 52.8 MB, 提交时间: 2023-09-20 11:25:25
class Solution {
public int minIncrementForUnique1(int[] A) {
// 先排序
Arrays.sort(A);
int move = 0;
// 遍历数组，若当前元素小于等于它的前一个元素，则将其变为前一个数+1
for (int i = 1; i < A.length; i++) {
if (A[i] <= A[i - 1]) {
int pre = A[i];
A[i] = A[i - 1] + 1;
move += A[i] - pre;
}
}
return move;
}
// 计数排序
public int minIncrementForUnique2(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;
}
// 线性探测法
int[] pos = new int [200000];
public int minIncrementForUnique(int[] A) {
Arrays.fill(pos, -1); // -1表示空位
int move = 0;
// 遍历每个数字a对其寻地址得到位置b, b比a的增量就是操作数。
for (int a: A) {
int b = findPos(a);
move += b - a;
}
return move;
}
// 线性探测寻址（含路径压缩）
private int findPos(int a) {
int b = pos[a];
// 如果a对应的位置pos[a]是空位，直接放入即可。
if (b == -1) {
pos[a] = a;
return a;
}
// 否则向后寻址
// 因为pos[a]中标记了上次寻址得到的空位，因此从pos[a]+1开始寻址就行了（不需要从a+1开始）。
b = findPos(b + 1);
pos[a] = b; // 寻址后的新空位要重新赋值给pos[a]哦，路径压缩就是体现在这里。
return b;
}
}
java 解法, 执行用时: 45 ms, 内存消耗: 57.9 MB, 提交时间: 2023-09-20 11:21:24
class Solution {
// 方法一：计数，当找到一个没有出现过的数的时候，将之前某个重复出现的数增加成这个没有出现过的数
public int minIncrementForUnique2(int[] nums) {
int[] count = new int[100001];
for (int x : nums) {
count[x]++;
}
int ans = 0, taken = 0;
for (int x = 0; x < 100001; ++x) {
if (count[x] >= 2) {
taken += count[x] - 1;
ans -= x * (count[x] - 1);
} else if (taken > 0 && count[x] == 0) {
taken--;
ans += x;
}
}
return ans;
}
// 方法二：排序对方法一优化
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[i]) {
taken++;
ans -= nums[i];
} else {
int give = Math.min(taken, nums[i] - 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;
}
}