2225-找出输掉零场或一场比赛的玩家

给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了
loseri 。

返回一个长度为 2 的列表 __answer ：

• answer[0] 是所有 没有 输掉任何比赛的玩家列表。
• answer[1] 是所有恰好输掉 一场 比赛的玩家列表。

两个列表中的值都应该按 递增 顺序返回。

注意：

• 只考虑那些参与 至少一场 比赛的玩家。
• 生成的测试用例保证 不存在 两场比赛结果 相同 。

示例 1：

**输入：** matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
**输出：** [[1,2,10],[4,5,7,8]]
**解释：**
玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。

示例 2：

**输入：** matches = [[2,3],[1,3],[5,4],[6,4]]
**输出：** [[1,2,5,6],[]]
**解释：**
玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。

提示：

• 1 <= matches.length <= 105
• matches[i].length == 2
• 1 <= winneri, loseri <= 105
• winneri != loseri
• 所有 matches[i] 互不相同

方法一：哈希表

思路与算法

我们可以用一个哈希映射记录每一名玩家输掉比赛的次数。对于哈希映射中的每一个键值对，键表示一名玩家，值表示该玩家输掉比赛的次数。

这样一来，我们只需要遍历数组 matches。当我们遍历到第 i 项 (\textit{winner}_i, \textit{loser}_i) 时，如果 winner}_i 或 loser}_i 没有在哈希映射中作为键出现过，那么我们需要把他们加入哈希映射中，并且对应的值为 0。随后，我们需要将 loser}_i 在哈希映射中对应的值增加 1，表示玩家 loser}_i 输掉了一场比赛。

在这之后，我们只需要再对哈希表进行一次遍历，「没有输掉任何比赛的玩家」即为所有值为 0 的键，「恰好输掉一场比赛的玩家」即为所有值为 1 的键。

代码

[sol1-C++]

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        unordered_map<int, int> freq;
        for (const auto& match: matches) {
            int winner = match[0], loser = match[1];
            if (!freq.count(winner)) {
                freq[winner] = 0;
            }
            ++freq[loser];
        }

        vector<vector<int>> ans(2);
        for (const auto& [key, value]: freq) {
            if (value < 2) {
                ans[value].push_back(key);
            }
        }

        sort(ans[0].begin(), ans[0].end());
        sort(ans[1].begin(), ans[1].end());
        return ans;
    }
};

[sol1-Python3]

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        freq = Counter()
        for winner, loser in matches:
            if winner not in freq:
                freq[winner] = 0
            freq[loser] += 1
        
        ans = [[], []]
        for key, value in freq.items():
            if value < 2:
                ans[value].append(key)
        
        ans[0].sort()
        ans[1].sort()
        return ans

复杂度分析

• 时间复杂度：O(n \log n)，其中 n 是数组 matches 的长度。

• 空间复杂度：O(n)，即为哈希映射需要使用的空间。