1 条题解
-
0
#include <bits/stdc++.h> using namespace std; /** * 主函数:利用集合的去重特性找出未到达的同学 * 输入:N(班级人数),M(报数次数),随后M个报出的编号 * 输出:若所有同学到达则输出N,否则输出未到达同学编号(升序排列) * 功能:用集合记录已报过编号的同学,遍历0\~N-1找出未出现的同学 */ int main() { int N, M; cin >> N >> M; // 使用集合自动去重,存储所有报出过的编号(不重复) unordered_set<int> reported; // [[6]][[9]] for (int i = 0; i < M; ++i) { int num; cin >> num; reported.insert(num); // 重复插入不影响结果,集合自动去重[[5]][[9]] } // 遍历所有同学编号,检查是否在集合中存在 vector<int> missing; for (int i = 0; i < N; ++i) { if (reported.find(i) == reported.end()) { // 若未报过该编号 missing.push_back(i); // 记录缺失同学[[7]][[9]] } } // 输出结果 if (missing.empty()) { cout << N << endl; // 全部到达时输出N[[1]][[6]] } else { for (size_t j = 0; j < missing.size(); ++j) { if (j != 0) cout << " "; // 空格分隔输出 cout << missing[j]; } cout << endl; } return 0; } /** * 思路总结: * 1. 集合自动去重:利用unordered_set存储报出过的编号,重复报数自动过滤[[5]][[7]]。 * 2. 缺失检测:遍历所有同学编号,若不在集合中则判定为未到达[[6]][[9]]。 * 3. 输出优化:直接按顺序遍历0\~N-1,无需额外排序,天然满足升序要求[[7]][[9]]。 * 该方法时间复杂度为O(M + N),空间复杂度O(K)(K为不同报数个数),在数据规模下效率与数组法相当。 */
- 1
信息
- ID
- 4858
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 2
- 标签
- (无)
- 递交数
- 25
- 已通过
- 9
- 上传者