6321.执行操作后地最大mex-337

执行操作后的最大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 <= 10^5
-10^9 <= nums[i] <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

需要找到其中的最小非负整数，第一个想法就是从零开始遍历，判断数组中是否存在一个数通过有限次加减操作后可以得到目标数。问题也就转换成快速判断一个数能否通过有限次加减value得到目标数，看到任意次数加减value可以马上反应到取模，如果两个数对value的余数相同，那么就可以通过有限次的加减相互转换了，这样就可以通过余数将数组中的不同元素分为不同类别，并且通过余数是否相同判断是否可以相互转化。补充一句，这种关系在数学上被称为同余，也就是余数相同，中间使用三条横线表示。

code

class Solution {
public:
    //任意元素加上或者减去value
    //找到其中缺失的最小非负整数
    
    //0,1,2,3,4......
    //可以不断循环判断是否存在或者有一些数可以转换为01234
    //快速判断是否存在以及是否可以转换
    //全部取余数
    //0 - value-1之间的值
    //缺失的值必然是0-value-1之间的值(不对哦，也可能是缺失较大的)
    //因为大于等于value的值都可以通过加value得到，0-value-1缺失的值也可以通过减去value得到
    //取余是为了快速判断是否可以加减得到，余数相同便是可以转换
    //全部取余,hashmap记录个数
    //0开始不断循环看看缺失哪个
    
    int findSmallestInteger(vector<int>& nums, int value) {
        
        unordered_map<int,int> cnt;
        
        for(auto item : nums) 
        {
            int res = item % value;
            if(res < 0) res += value;
            cnt[res] ++;
        }
        
        int mex = 0;
        while(1)
        {
            int res = mex % value;
            if(cnt.find(res) != cnt.end())
            {
                if(cnt[res] == 0) break;
                else
                {
                    cnt[res] --;
                    mex ++;
                }
            }
            else break;
        }
        
        return mex;
    }
};