ABC245B Mex

题目分析

• 给定长度为 $N$ 的整数序列 $A$，元素范围在 $0$ 到 $2000$ 之间；
• 需要找出最小的非负整数，且该整数不在序列中出现。

---

解题思路

• 用一个布尔数组 vis 来标记 $0$ 到 $2000$ 之间数字是否出现过；
• 遍历输入序列，将对应数字位置标记为出现；
• 从 $0$ 开始向上检查，找到第一个未出现的数字即为答案。

---

实现步骤

• 读入整数 $N$；
• 读入序列 $A$；
• 定义长度为 $2005$ 的布尔数组 vis，设为全局变量，初始均为 $0$；
• 遍历序列 $A$，将 vis[A[i]] = true；
• 从 $0$ 到 $2000$ 依次检查 vis 数组，其实循环 $0\sim N$ 也可以，因为 mex 必然不会超过 $N$：
  • 找到第一个为 0 的下标，即为答案。
  • if (vis[i] == 0) 说明 $i$ 没有出现直接输出即可。

复杂度分析

• 时间复杂度：$O(N)$，最多遍历输入和检查布尔数组；
• 空间复杂度：$O(N)$。

---

总结

• 利用布尔数组高效标记存在的数字；
• 直接遍历寻找最小缺失整数；
• 简单易实现，适合题目数据范围。