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

Medium

题目描述

给你一个整数数组 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 <= 10^5
matches[i].length == 2
1 <= winneri, loseri <= 10^5
winneri != loseri
所有 matches[i] 互不相同。

解题思路

这道题需要统计每个玩家的失败次数，然后根据失败次数分类。

思路分析

统计失败次数: 遍历所有比赛记录，统计每个玩家的失败次数。同时需要记录所有参与过比赛的玩家。
记录参与者: 除了统计失败次数，还需要确保所有参与过比赛的玩家都被考虑在内，包括那些从未失败的获胜者。
分类筛选: 根据失败次数进行分类：
- 失败0次的玩家加入结果的第一个列表
- 失败1次的玩家加入结果的第二个列表
排序输出: 最后对两个列表进行排序，确保按递增顺序返回。

实现方法

使用哈希表记录每个玩家的失败次数，初始值为0。遍历比赛记录时，失败者的计数+1，获胜者如果不存在则初始化为0。这样既统计了失败次数，又确保所有参与者都被记录。

最后遍历哈希表，根据失败次数将玩家分类并排序。

时间复杂度主要来自排序操作，空间复杂度取决于参与比赛的玩家数量。

代码实现

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        unordered_map<int, int> lossCount;
        
        // 统计每个玩家的失败次数
        for (const auto& match : matches) {
            int winner = match[0], loser = match[1];
            // 确保获胜者被记录（如果之前没有记录过）
            if (lossCount.find(winner) == lossCount.end()) {
                lossCount[winner] = 0;
            }
            // 失败者失败次数+1
            lossCount[loser]++;
        }
        
        vector<int> noLoss, oneLoss;
        
        // 根据失败次数分类
        for (const auto& pair : lossCount) {
            if (pair.second == 0) {
                noLoss.push_back(pair.first);
            } else if (pair.second == 1) {
                oneLoss.push_back(pair.first);
            }
        }
        
        // 排序
        sort(noLoss.begin(), noLoss.end());
        sort(oneLoss.begin(), oneLoss.end());
        
        return {noLoss, oneLoss};
    }
};

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        loss_count = {}
        
        # 统计每个玩家的失败次数
        for winner, loser in matches:
            # 确保获胜者被记录（如果之前没有记录过）
            if winner not in loss_count:
                loss_count[winner] = 0
            # 失败者失败次数+1
            loss_count[loser] = loss_count.get(loser, 0) + 1
        
        no_loss = []
        one_loss = []
        
        # 根据失败次数分类
        for player, losses in loss_count.items():
            if losses == 0:
                no_loss.append(player)
            elif losses == 1:
                one_loss.append(player)
        
        # 排序并返回
        return [sorted(no_loss), sorted(one_loss)]

public class Solution {
    public IList<IList<int>> FindWinners(int[][] matches) {
        Dictionary<int, int> lossCount = new Dictionary<int, int>();
        
        // 统计每个玩家的失败次数
        foreach (var match in matches) {
            int winner = match[0], loser = match[1];
            // 确保获胜者被记录（如果之前没有记录过）
            if (!lossCount.ContainsKey(winner)) {
                lossCount[winner] = 0;
            }
            // 失败者失败次数+1
            lossCount[loser] = lossCount.GetValueOrDefault(loser, 0) + 1;
        }
        
        List<int> noLoss = new List<int>();
        List<int> oneLoss = new List<int>();
        
        // 根据失败次数分类
        foreach (var pair in lossCount) {
            if (pair.Value == 0) {
                noLoss.Add(pair.Key);
            } else if (pair.Value == 1) {
                oneLoss.Add(pair.Key);
            }
        }
        
        // 排序
        noLoss.Sort();
        oneLoss.Sort();
        
        return new List<IList<int>> { noLoss, oneLoss };
    }
}

var findWinners = function(matches) {
    const losses = new Map();
    const players = new Set();
    
    for (const [winner, loser] of matches) {
        players.add(winner);
        players.add(loser);
        losses.set(loser, (losses.get(loser) || 0) + 1);
    }
    
    const noLosses = [];
    const oneLoss = [];
    
    for (const player of players) {
        const lossCount = losses.get(player) || 0;
        if (lossCount === 0) {
            noLosses.push(player);
        } else if (lossCount === 1) {
            oneLoss.push(player);
        }
    }
    
    return [noLosses.sort((a, b) => a - b), oneLoss.sort((a, b) => a - b)];
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间复杂度	O(n + k log k)
空间复杂度	O(k)

其中 n 是比赛场数，k 是参与比赛的玩家总数。时间复杂度中 O(n) 用于遍历比赛记录，O(k log k) 用于对结果列表排序。空间复杂度主要用于存储哈希表和结果列表。

题目描述#

解题思路#

思路分析#

实现方法#

代码实现#

复杂度分析#

相关题目#