class Solution {
public:
int findSmallestInteger(vector<int>& nums, int value) {
}
};
6321. 执行操作后的最大 MEX
给你一个下标从 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原站题解
golang 解法, 执行用时: 168 ms, 内存消耗: 11.9 MB, 提交时间: 2023-03-19 22:08:26
func findSmallestInteger(nums []int, m int) (mex int) {
cnt := map[int]int{}
for _, x := range nums {
cnt[(x%m+m)%m]++
}
for cnt[mex%m] > 0 {
cnt[mex%m]--
mex++
}
return
}
cpp 解法, 执行用时: 224 ms, 内存消耗: 117.8 MB, 提交时间: 2023-03-19 22:08:15
class Solution {
public:
int findSmallestInteger(vector<int> &nums, int m) {
unordered_map<int, int> cnt;
for (int x : nums)
++cnt[(x % m + m) % m];
int mex = 0;
while (cnt[mex % m]--)
++mex;
return mex;
}
};
java 解法, 执行用时: 58 ms, 内存消耗: 58.5 MB, 提交时间: 2023-03-19 22:08:04
class Solution {
public int findSmallestInteger(int[] nums, int m) {
var cnt = new HashMap<Integer, Integer>();
for (int x : nums)
cnt.merge((x % m + m) % m, 1, Integer::sum); // cnt[(x%m+m)%m]++
int mex = 0;
while (cnt.merge(mex % m, -1, Integer::sum) >= 0) // cnt[mex%m]-1 >= 0
++mex;
return mex;
}
}
python3 解法, 执行用时: 260 ms, 内存消耗: 35.4 MB, 提交时间: 2023-03-19 22:07:47
# 同余分组
class Solution:
def findSmallestInteger(self, nums: List[int], m: int) -> int:
cnt = Counter(x % m for x in nums)
mex = 0
while cnt[mex % m]:
cnt[mex % m] -= 1
mex += 1
return mex