题目

给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。

在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

示例 1：

输入：nums = [1,-10,7,13,6,8], value = 5 输出：4 解释：执行下述操作可以得到这一结果：

nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
nums[3] 减去 value 两次，nums = [1,0,2,3,6,8] nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。

示例 2：

输入：nums = [1,-10,7,13,6,8], value = 7 输出：2 解释：执行下述操作可以得到这一结果：

nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8] nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。

提示：

1 <= nums.length, value <= 10^5
-10^9 <= nums[i] <= 10^9

解题思路

这道题的关键在于理解一个核心性质：对一个数 n 加上或减去任意次 value，其结果除以 value 的余数永远不会改变。

用数学公式表达就是： (n + k * value) % value = n % value

其中 k 是任意整数。

这个性质意味着，无论我们如何操作 nums 数组中的一个元素，它都永远被“锁定”在了它原始的“余数分组”里。例如，如果 value = 5，一个初始值为 7 的数（余数为 2）可以变成 2, 12, -3, -8 等等，但这些数除以 5 的余数永远是 2。它永远无法变成一个除以 5 余数是 3 的数（比如 3, 8, 13 等）。

有了上面的洞察，问题就可以被重新定义：

原问题：我们能构造出的连续非负整数序列 0, 1, 2, ..., k-1 最长是多少？（这个 k 就是最大的 MEX）

新问题：我们有一堆“原材料”（nums 里的数），这些原材料根据它们对 value 的余数被分成了 value 个不同的组。我们要构造目标 0, 1, 2, ...。

想构造 0，需要一个余数为 0 % value 的原材料。
想构造 1，需要一个余数为 1 % value 的原材料。
...
想构造 k，需要一个余数为 k % value 的原材料。

每个原材料只能使用一次。我们的目标是看这个构造过程能持续多久。

具体代码

func findSmallestInteger(nums []int, value int) int {

    // 统计每个余数有几个
    remain_vec := make([]int, value)

    // 遍历nums，填充上面的统计数组
    for _, num := range nums {
        // 算出正余数，然后给对应的计数器加一
        remain_vec[((num % value) + value) % value]++
    }

    // 找出哪个余数的数量最少
    min_index := 0 // 数量最少的那个余数
    min_value := remain_vec[0] // 最少的数量
    for index, count := range remain_vec {
        if count < min_value {
            min_index = index
            min_value = count
        }
    }

    // 瓶颈数量 * value + 瓶颈余数 就是答案
    return min_value * value + min_index
}

2598. 执行操作后的最大 MEX

beautifulremi

题目

解题思路

具体代码