日期: 2025 年 10 月 16 日

目标

给你一个下标从 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，求数组中缺失的最小非负整数的最大值。

关键点是想清楚，只要余数相同就能够操作成该数字，剩下的就是对余数的计数了。

代码

/**
 * @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++;
        }
    }

}

性能