执行操作后的最大 MEX

标签: 贪心 数组 哈希表 数学

难度: Medium

给你一个下标从 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

Submission

运行时间: 77 ms

内存: 28.4 MB

class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        v = set()
        cnts = collections.Counter()
        for x in nums:
            cnts[x%value]+=1
        mncnt = float('inf')
        mni = -1
        for i in range(value):
            if cnts[i] < mncnt:
                mni = i
                mncnt = cnts[i]
        return mni+value*mncnt

Explain

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

时间复杂度: O(n + value)

空间复杂度: O(value)

# 定义解决方案类

class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        # 初始化一个集合和计数器
        v = set()
        cnts = collections.Counter()
        # 计算nums中每个元素对value取模的计数
        for x in nums:
            cnts[x%value]+=1
        # 初始化最小计数和对应的模值索引
        mncnt = float('inf')
        mni = -1
        # 找到计数最少的模值
        for i in range(value):
            if cnts[i] < mncnt:
                mni = i
                mncnt = cnts[i]
        # 计算最终的MEX值
        return mni+value*mncnt

Explore

取模操作将元素按照对value的余数进行分类，这样每个类别中的元素可以通过加减value的倍数自由地变换到任何其他同余的数。这意味着，对于每个余数类别，我们可以通过适当的加减操作，生成从该余数开始的、间隔为value的数列。因此，对每个余数类别进行计数，可以帮助我们了解在进行加减操作后哪些数值是可达的，从而确定哪些数值是不可达的，这样我们就可以找到最小的不可达数，即MEX。

选择最小计数的余数来计算MEX是为了确保在对nums中的元素进行可能的操作后，能够生成尽可能大的不在数组中的非负整数。通过识别出现次数最少的余数，我们可以确定这个余数类别是最容易达到其上限（即通过连续加value无法生成更多新整数的点）的类别。这样，我们可以使用该余数和它的计数来计算出最大的MEX，而直接搜索未出现的最小非负整数则无法考虑到通过操作能够实现的数值变化，无法确保找到的是最大的MEX。

通过增加value的倍数来调整MEX的核心在于，任何数x加上或减去value的倍数，仍然保持相同的模value结果。这意味着在给定模value的余数情况下，我们可以通过增加相应余数的倍数，连续地生成一系列特定余数的数。例如，如果某个余数计数最小，则我们可以从这个余数开始，连续地加上value，生成一系列新的数，直到达到一个数，这个数通过加value无法从nums中任何其他数生成。这个过程允许我们找到最大的不可达数，即MEX。因此，识别最小计数的余数并计算基于这个余数的连续数列的上限，为我们提供了一个方法来确保我们计算的MEX是准确和最大的。