Back to Leetcode

Readme

Greedy/2598.Smallest-Missing-Non-negative-Integer-After-Operations/Readme.md

latest1.0 KB
Original Source

2598.Smallest-Missing-Non-negative-Integer-After-Operations

显然,对一个元素无论做多少次的加减操作,不变的就是对value的余数。于是,我们知道,只要有元素对value的余数是0,我们就可以构造出0来。同理,只要有元素对value的余数是1,我们就可以构造出1来。以此类推,我们可以推出是否能构造出value-1.

假设以上这些都可以构造出来,那么接下来就考虑能否构造出value来呢?其实只要再来一个能被value整除的元素,我们就可以构造出value来。同理,只要再有一个元素对value的余数是1,那么我们就可以调整它变成value+1,以此类推。

所以我们将所有元素以对value的模分类,找到其中的最小频次c以及对应的模r,就意味着我们能构造出c个[0, value-1]的完整周期来,也就是能构造出[0, value*c-1]的所有整数。接下来再算上零头,我们可以再构造出接下来r个元素。最终未能构造出的MEX就是value*c+r.