leetcode
leetcode 1151 ~ 1200
找出输掉零场或一场比赛的玩家

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

难度:

标签:

题目描述

代码结果

运行时间: 177 ms, 内存: 56.5 MB


/*
 * 题目思路:
 * 1. 使用Java Stream API来处理比赛数据。
 * 2. 首先通过流来记录每个玩家的获胜和失败次数。
 * 3. 过滤出没有失败的玩家和恰好失败一次的玩家。
 * 4. 对两个结果列表进行排序并返回。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        // 记录玩家的失败次数
        Map<Integer, Long> loseCount = Arrays.stream(matches)
            .collect(Collectors.groupingBy(match -> match[1], Collectors.counting()));

        // 记录玩家的获胜次数
        Set<Integer> winners = Arrays.stream(matches)
            .map(match -> match[0])
            .collect(Collectors.toSet());

        List<Integer> noLosses = winners.stream()
            .filter(player -> !loseCount.containsKey(player))
            .sorted()
            .collect(Collectors.toList());

        List<Integer> oneLoss = loseCount.entrySet().stream()
            .filter(entry -> entry.getValue() == 1)
            .map(Map.Entry::getKey)
            .sorted()
            .collect(Collectors.toList());

        return Arrays.asList(noLosses, oneLoss);
    }
}

解释

方法:

题解首先使用Counter来统计每个玩家输掉的比赛次数,其中loser统计的是比赛数据中每个loser输掉的比赛次数。接着,创建一个winner的集合来收集所有赢过的玩家。然后,遍历winner集合,对于那些不在loser字典中的玩家,即未输过比赛的玩家,将他们加入到结果列表res[0]中。对于res[1],直接通过列表推导查找loser字典中输掉恰好一场比赛的玩家。最后,对两个结果列表进行排序,确保返回的列表是递增顺序。

时间复杂度:

O(n + k log k + m log m)

空间复杂度:

O(n)

代码细节讲解

🦆
题解中提到使用Counter来统计每个玩家输掉的比赛次数,但如何确保每位玩家在matches列表中只被统计一次?
在题解中,Counter 是用于统计每位玩家在比赛数据列表中作为loser出现的次数。Counter 会对列表中的每个元素进行计数,因此如果一个玩家在多场比赛中输了,则每次输掉的比赛都会被统计。这里的“每位玩家只被统计一次”指的是每场比赛的输家在统计时不会被遗漏,也不会因为比赛数据的问题而重复统计同一场比赛,但如果玩家在多场比赛中输掉,每场输掉的都会被计入总次数。
🦆
题解中未提及如何处理那些即是winner又是loser的玩家,他们应该如何分类到相应的列表中?
在题解算法中,如果一个玩家在某些比赛中是winner而在其他比赛中是loser,他们的分类将依据题目的具体要求。根据题解,首先检查一个玩家是否作为winner存在且没有在loser字典中,则将其加入到未输过任何比赛的玩家列表中。对于输掉一场比赛的分类,只会查看loser字典中输掉恰好一场比赛的玩家。因此,一个玩家即使赢过比赛,只要他在loser字典中输掉恰好一场,仍然会被加入到输掉一场比赛的列表中。
🦆
在题解中,为何选择使用set来收集所有的winner而不是继续使用Counter,这样做有什么特别的好处吗?
使用set而不是Counter来收集所有的winner可以有效避免重复并且减少不必要的信息存储。因为在这个特定问题中,我们只关心每个玩家是否赢过比赛,而不关心他们赢了多少场比赛。set自然提供了元素唯一性的保证,这对于识别未输过比赛的玩家来说是足够的。如果使用Counter,虽然也能实现相同的功能,但会额外记录每位玩家赢的次数,这在本题中是不必要的信息。

相关问题