LeetCode 题解工作台
执行操作后的最大 MEX
给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。 在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3]…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用哈希表 统计数组中每个数对 取模后的余数的个数。 然后从 开始遍历，对于当前遍历到的数 ，如果 $\textit{cnt}[i \bmod \textit{value}]$ 为 ，说明数组中不存在一个数对 取模后的余数为 ，那么 就是数组的 MEX，直接返回即可。否则，将 $\textit{cnt}[i \bmod \textit{value}]$ 减 ，继续遍历。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 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 <= 105-109 <= nums[i] <= 109
解题思路
方法一：计数
我们用哈希表 统计数组中每个数对 取模后的余数的个数。
然后从 开始遍历，对于当前遍历到的数 ，如果 为 ，说明数组中不存在一个数对 取模后的余数为 ，那么 就是数组的 MEX，直接返回即可。否则，将 减 ，继续遍历。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def findSmallestInteger(self, nums: List[int], value: int) -> int:
cnt = Counter(x % value for x in nums)
for i in range(len(nums) + 1):
if cnt[i % value] == 0:
return i
cnt[i % value] -= 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + value) due to scanning nums and checking counts for each remainder. Space complexity is O(value) for storing remainder frequencies in a hash map. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Notice how repeated additions and subtractions reduce to modular arithmetic.
- question_mark
Watch for large negative numbers; handle mapping modulo correctly.
- question_mark
Think about a greedy sequential scan to identify the first missing integer efficiently.
常见陷阱
外企场景- error
Failing to handle negative numbers correctly when computing modulo.
- error
Assuming numbers outside initial array cannot become smaller after operations.
- error
Iterating without counting remainders can lead to incorrect MEX computation.
进阶变体
外企场景- arrow_right_alt
Compute largest reachable number with repeated add/subtract operations.
- arrow_right_alt
Find MEX after performing operations only on a subset of array indices.
- arrow_right_alt
Determine MEX when each number has a distinct operation value instead of a single value.