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

Categories:

题目描述
思路分析
1. 解法一：排序 + 贪心（推荐）
相似题目

题目描述

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

思路分析

解法一：排序 + 贪心（推荐）

核心思路：

排序后依次保证当前值至少为 prev + 1。

若当前值小于等于 prev，则增加到 prev + 1 并累加增量。

更新 prev 为调整后的值。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(1) 额外空间（排序除外）。

import java.util.Arrays;

class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);
        int moves = 0;
        int prev = Integer.MIN_VALUE;

        for (int num : nums) {
            int target = Math.max(num, prev + 1);
            moves += target - num;
            prev = target;
        }

        return moves;
    }
}

import "sort"

func minIncrementForUnique(nums []int) int {
	sort.Ints(nums)
	moves := 0
	prev := -1 << 60

	for _, num := range nums {
		target := num
		if target <= prev {
			target = prev + 1
		}
		moves += target - num
		prev = target
	}

	return moves
}

相似题目

题目	难度	考察点
455. 分发饼干	简单	排序 + 贪心
621. 任务调度器	中等	贪心
135. 分发糖果	困难	贪心
1051. 高度检查器	简单	排序
1798. 你能构造出连续值的最大数目	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/68576875