执行操作后的最大 MEX

You are given a 0-indexed integer array nums and an integer value.

In one operation, you can add or subtract value from any element of nums.

• For example, if nums = [1,2,3] and value = 2, you can choose to subtract value from nums[0] to make nums = [-1,2,3].

The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it.

• For example, the MEX of [-1,2,3] is 0 while the MEX of [1,0,3] is 2.

Return the maximum MEX of nums after applying the mentioned operation any number of times.

 

Example 1:

Input: nums = [1,-10,7,13,6,8], value = 5
Output: 4
Explanation: One can achieve this result by applying the following operations:
- Add value to nums[1] twice to make nums = [1,0,7,13,6,8]
- Subtract value from nums[2] once to make nums = [1,0,2,13,6,8]
- Subtract value from nums[3] twice to make nums = [1,0,2,3,6,8]
The MEX of nums is 4. It can be shown that 4 is the maximum MEX we can achieve.

Example 2:

Input: nums = [1,-10,7,13,6,8], value = 7
Output: 2
Explanation: One can achieve this result by applying the following operation:
- subtract value from nums[2] once to make nums = [1,-10,0,13,6,8]
The MEX of nums is 2. It can be shown that 2 is the maximum MEX we can achieve.

 

Constraints:

• 1 <= nums.length, value <= 105
• -109 <= nums[i] <= 109

/*
 * 思路：
 * 1. 使用 Java Stream API 计算每个元素的模 value 的值。
 * 2. 使用 Collectors.toSet() 将这些模值收集到一个 set 中。
 * 3. 使用 IntStream.range 迭代 0 到 value-1，找到第一个不存在的模值。
 */
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MaxMEXStream {
    public int findMaxMEX(int[] nums, int value) {
        Set<Integer> modSet = IntStream.of(nums)
                .map(num -> ((num % value) + value) % value) // 保证模数为正
                .boxed()
                .collect(Collectors.toSet());
        return IntStream.range(0, value)
                .filter(i -> !modSet.contains(i))
                .findFirst()
                .orElse(value); // 如果 0 到 value-1 都存在，最大 MEX 为 value
    }
}

题解的核心思路是利用模运算来分组处理数组中的元素。由于任何元素都可以通过加减给定的值value来改变，因此可以观察到，对于任何数字x，x%value的结果是有限的，从0到value-1。因此，可以利用这个性质来求解最小的非出现整数（MEX）。首先，通过遍历数组nums，使用哈希表（这里使用collections.Counter）来记录每个可能的余数值出现的次数。然后，找到拥有最小计数的余数，这样可以确保在对nums进行操作后，能够得到最大的MEX值。最后，根据这个余数和它的计数，可以计算出MEX。这种方法有效地利用了模运算的性质来简化问题，避免了直接寻找缺失的最小非负整数这一复杂过程。

O(n + value)

O(value)