题目内容

小欧有一个长度为$n$的数组$[a_1,a_2,...,a_n]$。现在他想知道，对于$a$中的每个元素，删除该元素后数组的MEX值是多少，请你帮他算算吧。

整数数组的MEX定义为没有出现在数组中的最小非负整数。

MEX数组

题解思路

1. 首先使用哈希表统计数组中各个数字出现的次数。
2. 计算整体数组的 MEX 值：
   • 从 0 开始，如果数字 0 出现在数组中，则 MEX 至少为 1；继续判断 1、2、…，直到遇到第一个未出现的数字，此时该数字即为整体数组的 MEX。
3. 对于数组中每个位置，如果删除该位置的元素会改变整体 MEX：
   • 如果当前元素的值小于整体 MEX 且该数字在数组中只出现一次，则删除后该数字从数组中消失，变成缺失的最小非负整数，此时删除后的 MEX 就变为该数字；
   • 否则，删除后数组中仍然包含该数字或该数字本身不影响整体 MEX，删除后的 MEX 与整体 MEX 相同。
4. 最后输出每个位置删除后得到的 MEX 值。