leetcode
leetcode 851 ~ 900
使数组唯一的最小增量

使数组唯一的最小增量

难度:

标签:

题目描述

代码结果

运行时间: 149 ms, 内存: 33.7 MB


/*
 * 思路:
 * 1. 首先对数组进行排序。
 * 2. 然后使用Stream API遍历数组,从第二个元素开始,如果当前元素小于等于前一个元素,
 *    则将当前元素增加到前一个元素加1,记录增加的次数。
 * 3. 最后返回总共增加的次数。
 */
import java.util.Arrays;

public class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums); // 对数组进行排序
        int[] prev = {nums[0]}; // 记录前一个元素的值
        int[] moves = {0}; // 记录操作次数
        Arrays.stream(nums, 1, nums.length).forEach(num -> {
            if (num <= prev[0]) { // 如果当前元素小于等于前一个元素
                int increment = prev[0] + 1 - num; // 计算需要增加的量
                moves[0] += increment; // 累加操作次数
                prev[0] = num + increment; // 更新前一个元素的值
            } else {
                prev[0] = num; // 更新前一个元素的值
            }
        });
        return moves[0]; // 返回总操作次数
    }
}

解释

方法:

此题解采用了一个分步处理的策略:首先,通过遍历数组并使用一个集合来标记所有已经存在的数字,同时记录所有重复的数字到一个列表中。之后,对这个列表进行排序,然后对于列表中的每个数字,寻找一个尚未使用的最小数字使得该数字变得唯一。这通过逐渐增加一个目标数字并检查它是否被占用来实现。每次找到一个合适的数字后,计算增加的步数,并将此目标数字标记为已使用。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
在题解中提到的集合用于存储每个独特的数字,为什么不直接在数组内部操作而选择使用额外的数据结构?
使用集合来存储独特的数字可以快速检查一个数字是否已存在,这是因为集合提供了平均时间复杂度为O(1)的查找效率。如果直接在数组内部操作,例如通过搜索或排序来检查唯一性,这将导致更高的时间复杂度,特别是在数组较大时。使用集合可以显著提高算法的效率和响应速度。
🦆
你是如何确定重复数字列表`f`的初始值应该设置为`x + 1`,而不是其他值?
在设定重复数字列表`f`的初始值为`x + 1`时,基本思路是尝试将重复的数字`x`增加到它的下一个可能的最小唯一值。这是因为任何小于`x`的值都已经被`x`或之前的数字占据,而`x + 1`是第一个可能未被占据的值,从而使得步数最小化。这样的设置有助于直接定位到可能的最小可用数字,减少不必要的迭代和检查。
🦆
为什么在处理重复数字时,选择对它们进行排序?这种排序对算法的性能优化有什么具体影响?
对重复数字进行排序可以帮助算法按照从小到大的顺序处理它们,这样可以有效地利用已标记为占用的数字集合`set`,并且避免在寻找下一个可用数字时反复回溯。通过排序,我们可以保证每次处理的数字都是当前未处理的最小值,从而使得寻找下一个可用数字时,能够从前一个已经确定位置的数字顺畅过渡,减少了查找的次数,提高了算法的整体效率。
🦆
在解决方案中,每次找到一个未使用的数字后,都会进行`target += 1`的操作直到找到可用位置,这种方法在最坏情况下的性能如何?
在最坏的情况下,如果数组中的数字非常密集或有大量重复,`target`可能需要连续增加多次才能找到一个未被使用的数字。这种情况下,每次增加`target`都可能涉及对集合`s`的查找操作,每个查找的时间复杂度为O(1),但若重复次数多,则整体性能会受到影响。尽管如此,通过使用集合结合排序,该方法通常还是比没有优化的直接处理要高效。

相关问题