题目解析
* 输入输出:第一行输入两个整数 NNN(班级人数,编号 000 到 N−1N-1N−1)和 MMM(报数总次数);第二行输入 MMM 个整数表示每次报出的编号。输出所有未到达同学的编号(升序,空格分隔);若全部到达,则只输出一个整数 NNN。
* 数据范围:2≤N,M≤1002 \le N, M \le 1002≤N,M≤100,所有报出的编号均在 [0,N−1][0, N-1][0,N−1] 范围内。
* 复杂度要求:数据规模极小,线性 O(N+M)O(N+M)O(N+M) 时间复杂度和 O(N)O(N)O(N) 空间复杂度即可轻松满足 1s1\text{s}1s 时限与 128MB128\text{MB}128MB 内存限制。
* 算法知识点:数组计数(桶思想)、简单模拟、集合差集
思路解析
1. 建立存在性标记:创建一个大小足够的计数数组 cnt(初始化为0),遍历 MMM 次报数记录。对于每次报出的编号 xxx,执行 cnt[x]++。由于题目只关心"是否到达"而不关心次数,只要 cnt[x] > 0 即表示该同学已到达。
2. 遍历检查缺失:顺序扫描编号 000 到 N−1N-1N−1。若 cnt[i] == 0,说明编号 iii 的同学从未报数,即未到达,立即输出该编号;同时用变量 ans 统计已到达的人数(即 cnt[i] > 0 的情况)。
3. 处理全到达情况:扫描结束后,若 ans == n,说明 000 到 N−1N-1N−1 所有编号均存在,按题意输出 NNN。
完整代码