2598.执行操作后的最大MEX

链接：2598.执行操作后的最大MEX
难度：Medium
标签：贪心、数组、哈希表、数学
简介：返回在执行上述操作 任意次 后，nums 的最大 MEX 。

题解 1 - cpp

• 编辑时间：2023-03-19
• 执行用时：224ms
• 内存消耗：117.9MB
• 编程语言：cpp
• 解法介绍：先对所有数字进行取模归并，再依次寻找。

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        unordered_map<int,int> m;
        for (auto &num: nums) m[(num % value + value) % value]++;
        for (int i = 0; ;i++) {
            if (m[i%value]) m[i%value]--;
            else return i;
        }
        return 0;
    }
};

题解 2 - rust

• 编辑时间：2023-03-19
• 执行用时：56ms
• 内存消耗：6.6MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn find_smallest_integer(nums: Vec<i32>, value: i32) -> i32 {
        let mut m = std::collections::HashMap::<i32, usize>::new();
        for num in nums {
            *m.entry((num % value + value) % value).or_insert(0) += 1;
        }
        let mut i = 0;
        loop {
            let item = m.get_mut(&(i % value));
            if let Some(v) = item {
                if *v == 0 {
                    return i;
                } else {
                    *v -= 1;
                }
            } else {
                return i as i32;
            }
            i += 1;
        }
    }
}

题解 3 - python

• 编辑时间：2023-03-19
• 执行用时：356ms
• 内存消耗：35.3MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        m = Counter()
        for num in nums:
            m[(num % value + value) % value] += 1
        i = 0
        while True:
            if m[i % value]:
                m[i % value] -= 1
            else:
                return i
            i += 1