Question

2598. 执行操作后的最大 MEX

English Version

题目描述

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

解法

方法一：计数

我们用哈希表或数组 $cnt$ 统计数组中每个数对 $value$ 取模后的余数的个数。

然后从 $0$ 开始遍历，对于当前遍历到的数 $i$，如果 $cnt[i \bmod value]$ 为 $0$，说明数组中不存在一个数对 $value$ 取模后的余数为 $i$，那么 $i$ 就是数组的 MEX，直接返回即可。否则，将 $cnt[i \bmod value]$ 减 $1$，继续遍历。

时间复杂度 $O(n)$，空间复杂度 $O(value)$。其中 $n$ 为数组 $nums$ 的长度。

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

class Solution {
  public int findSmallestInteger(int[] nums, int value) {
    int[] cnt = new int[value];
    for (int x : nums) {
      ++cnt[(x % value + value) % value];
    }
    for (int i = 0;; ++i) {
      if (cnt[i % value]-- == 0) {
        return i;
      }
    }
  }
}

class Solution {
public:
  int findSmallestInteger(vector<int>& nums, int value) {
    int cnt[value];
    memset(cnt, 0, sizeof(cnt));
    for (int x : nums) {
      ++cnt[(x % value + value) % value];
    }
    for (int i = 0;; ++i) {
      if (cnt[i % value]-- == 0) {
        return i;
      }
    }
  }
};

func findSmallestInteger(nums []int, value int) int {
  cnt := make([]int, value)
  for _, x := range nums {
    cnt[(x%value+value)%value]++
  }
  for i := 0; ; i++ {
    if cnt[i%value] == 0 {
      return i
    }
    cnt[i%value]--
  }
}

function findSmallestInteger(nums: number[], value: number): number {
  const cnt: number[] = new Array(value).fill(0);
  for (const x of nums) {
    ++cnt[((x % value) + value) % value];
  }
  for (let i = 0; ; ++i) {
    if (cnt[i % value]-- === 0) {
      return i;
    }
  }
}