给你一个下标从 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的,但是熟练度不够,有点遗憾.
标签：周赛,13,LC,P4,nums,value,x%,m1,MEX From： https://www.cnblogs.com/remarkableboy/p/17265945.html