C++实现马拉松未完赛选手排查代码异常求助

需求是从马拉松参赛者列表和完赛者列表中找出未完赛的选手，核心逻辑用map统计选手出现次数，但运行结果异常。

约束条件：

• 参赛者人数在1到100000之间
• 完赛者列表长度比参赛者列表少1
• 参赛者名称由1到20个小写英文字母组成
• 允许存在同名参赛者

现有代码 #

#include <vector>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    map<string, int> playerMap;

    for (auto player : participant)++playerMap[player];
    for (auto player : completion)
    {
        --playerMap[player];
        if (playerMap[player] == 1)
            return player;
    }

}

问题原因分析 #

1. 核心逻辑判断错误：遍历完赛者列表时，每减一次计数就判断是否等于1并返回，这和需求完全不符。比如某选手参赛2次、完赛1次，计数从2变为1时会被错误返回，但该选手实际有1次完赛、1次未完赛，真正的未完赛选手需要等所有完赛者计数扣除完毕后，找最终计数大于0的对象。
2. 函数无默认返回值：如果循环结束后未触发返回，函数会返回未定义的字符串，导致运行时异常行为。

修正后的代码 #

#include <vector>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    map<string, int> playerMap;

    // 统计所有参赛者的出现次数
    for (const auto& player : participant) {
        playerMap[player]++;
    }

    // 扣除完赛者的次数
    for (const auto& player : completion) {
        playerMap[player]--;
    }

    // 找到最终计数大于0的选手（即未完赛的）
    for (const auto& pair : playerMap) {
        if (pair.second > 0) {
            return pair.first;
        }
    }

    // 按约束条件不会走到此处，返回空字符串避免编译警告
    return "";
}

可选优化 #

如果追求更高性能，可改用unordered_map替代map——unordered_map的插入、查找操作平均时间复杂度为O(1)，而map为O(log n)，对于10万级别的数据量，性能差异会比较明显。

内容的提问来源于stack exchange，提问作者Hyeong ju kim