[每日一题] 2225.找出输掉零场或一场比赛的玩家

博主： Richard
发布时间：2024 年 05 月 22 日
104 次浏览
暂无评论
1755字数
分类： LeetCode

> https://leetcode.cn/problems/find-players-with-zero-or-one-losses/description/?envType=daily-question&envId=2024-05-02

直接用哈希表统计没输过，输了一次，输了多次的玩家即可。

```c++
class Solution {
public:
    std::vector<std::vector<int>> findWinners(std::vector<std::vector<int>> &matches) {
        std::set<int> first, second, other;

for (auto &match: matches) {
            if (first.find(match[0]) == first.end() && second.find(match[0]) == second.end() &&
                other.find(match[0]) == other.end())
                first.insert(match[0]);

if (first.find(match[1]) != first.end()) {
                first.erase(match[1]);
                second.insert(match[1]);
            } else if (second.find(match[1]) != second.end()) {
                second.erase(match[1]);
                other.insert(match[1]);
            } else if (other.find(match[1]) == other.end()){
                second.insert(match[1]);
            }
        }

return {std::vector<int>(first.begin(), first.end()), std::vector<int>(second.begin(), second.end())}; 
    }
};
```

- 时间复杂度：$O(nlogn)$ ，其中 $n$ 为比赛数。
- 空间复杂度：$O(n)$ 。

当然也可以用哈希表记录每一位玩家输掉的次数，会比上面的方法更快一些：

```c++
class Solution {
public:
    std::vector<std::vector<int>> findWinners(std::vector<std::vector<int>> &matches) {
        std::unordered_map<int, int> results;

for (auto &match : matches) {
            results[match[0]];
            ++results[match[1]];
        }

std::vector<std::vector<int>> res(2);
        for (auto &[key, value] : results) {
            if (value < 2)
                res[value].push_back(key);
        }
      
        std::sort(res[0].begin(), res[0].end());
        std::sort(res[1].begin(), res[1].end());
      
        return res;
    }
};
```

- 时间复杂度：$O(nlogn)$ ，其中 $n$ 为比赛数。
- 空间复杂度：$O(n)$ 。

最后修改：2024 年 05 月 22 日