目标
给你一个下标从 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
思路
有一个数组，可以执行 任意 次操作，每次操作可以将任意元素加上或者减去 value，求数组中缺失的最小非负整数的最大值。
题目要求返回缺失的最小非负整数，可以从 0 开始枚举每一个整数 target，问题是如何判断数组中是否存在元素 nums[i] + k * value == target。两边同时对 value 取余可得 nums[i] ≡ target (mod value)。
可以对 nums[i] % value 计数，枚举 target 判断是否还剩有同余元素即可。
代码
/**
* @date 2025-10-16 8:46
*/
public class FindSmallestInteger2598 {
public int findSmallestInteger(int[] nums, int value) {
int[] cnt = new int[value];
for (int num : nums) {
int rem = num % value;
rem = rem >= 0 ? rem : rem + value;
cnt[rem]++;
}
int res = 0;
while (true) {
int rem = res % value;
if (cnt[rem] > 0) {
cnt[rem]--;
} else {
return res;
}
res++;
}
}
}
性能
