给你一个下标从 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
思路:若存在三个数nums[i],nums[j],value使得nums[j] = k*value+nums[i],其中k∈R,则nums[j]%value=nums[i]%value,称之为同余定理,本题利用一个map<int,vector<int>>存下所有key为nums[i]%value的nums,对于第x个数,x∈[0,+∞)来说,如x不在nums中,则找与x同余的数替代它.
class Solution { unordered_map<int,int> m; unordered_map<int,vector<int>> m1;//如果用不到map的排序特性建议开无序hash,能省不少时间开销. public: int findSmallestInteger(vector<int>& nums, int value) { for(auto i=0;i<nums.size();i++)//先让小于0的数变成正数 { if(nums[i]<0) { int k = (abs(nums[i])+value-1)/value; nums[i]+=(value*k); } } for(auto i=0;i<nums.size();i++)//存下同余的数 { m1[nums[i]%value].push_back(nums[i]); } for(auto i=0;i<nums.size();i++)//这里作用为快速查询nums里有没有这个数 { m[nums[i]]++; } int x = 0; while(1)//从0开始找 { if(m[x]<=0) { if(m1[x%value].size()>0)//若果有同余的数,用掉这个数 { m.erase(m1[x%value][m1[x%value].size()-1]); m1[x%value].pop_back(); x+=1; continue; } else//没有直接return { return x; } } else//若在nums里有x则用掉x { auto it =find(m1[x%value].begin(),m1[x%value].end(),x); m1[x%value].erase(it); x+=1; } } return 1; } };
赛后感想:本来这场能ak的,但是熟练度不够,有点遗憾.