1 条题解

  • 0
    @ 2025-4-6 15:36:03
    #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
    上传者