2598. 執行操作後的最大MEX

思路

目標要找到操作任意次過後，數組缺失的最小非負整數，
由於能操作任意次，又要讓缺失的數字盡量大，
因此能設定目標數字從 0 開始，逐漸往上提高，看能不能將數字經過任意次操作之後變成目標數字。

1. 假設目標數字為target，判斷現在的數字nums[i]能否變成target，需要滿足(target - nums[i]) % value == 0。
2. 假設一個數字nums[i]能變成target，那麼它也能變成target + n * value（n為任意整數）。

因此，數字num[i]跟nums[i] + n * value能視為同樣的數字。
舉例來說，若value = 5，nums[0] = 3，nums[1] = -2，
由於兩者相差為1 * value，能視為相同的數字，都能夠填補「能表示為3 + n * value的數字」。

將目標數字從零開始往上找，假如有數字能夠填補，便消耗掉一次使用次數。
如果使用次數不足夠，表示無法填補，找到答案。

假如使用次數完全足夠，沒有缺失，相當於整個數組的形式能轉變為0 ~ n - 1的一個排列，所求為n

程式碼

哈希表

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        int n = nums.size();
        for(int x : nums) {
            if(x < 0) {
                if(x % value)
                    ++freq[value + x % value];
                else {
                    ++freq[0];
                }
            }
            else {
                ++freq[x % value];
            } 
        }
        for(int target = 0; target < n; ++target) {
            if(freq[target % value] <= 0) return target;
            --freq[target % value];
        }
        // 沒有缺失
        return n; 
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$