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

标签: 数组 哈希表 计数 排序

难度: 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 <= 105
  • matches[i].length == 2
  • 1 <= winneri, loseri <= 105
  • winneri != loseri
  • 所有 matches[i] 互不相同

Submission

运行时间: 177 ms

内存: 56.5 MB

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        loser = Counter([pair[1] for pair in matches])
        winner = set([pair[0] for pair in matches])
        res = [[], []]
        for w in winner:
            if w not in loser:
                res[0].append(w)
        res[0].sort()
        res[1] = [x for x, n in loser.items() if n == 1]
        res[1].sort()
        return res

Explain

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

时间复杂度: O(n + k log k + m log m)

空间复杂度: O(n)

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        # 使用Counter来计算每个loser输掉的比赛次数
        loser = Counter([pair[1] for pair in matches])
        # 使用set来收集所有的winner，避免重复
        winner = set([pair[0] for pair in matches])
        # 初始化结果列表
        res = [[], []]
        # 查找没有输掉任何比赛的玩家
        for w in winner:
            if w not in loser:
                res[0].append(w)
        # 排序，以符合题目要求的递增顺序
        res[0].sort()
        # 利用列表推导找出恰好输掉一场比赛的玩家
        res[1] = [x for x, n in loser.items() if n == 1]
        # 排序
        res[1].sort()
        # 返回结果
        return res

Explore

在题解中，Counter 是用于统计每位玩家在比赛数据列表中作为loser出现的次数。Counter 会对列表中的每个元素进行计数，因此如果一个玩家在多场比赛中输了，则每次输掉的比赛都会被统计。这里的“每位玩家只被统计一次”指的是每场比赛的输家在统计时不会被遗漏，也不会因为比赛数据的问题而重复统计同一场比赛，但如果玩家在多场比赛中输掉，每场输掉的都会被计入总次数。

在题解算法中，如果一个玩家在某些比赛中是winner而在其他比赛中是loser，他们的分类将依据题目的具体要求。根据题解，首先检查一个玩家是否作为winner存在且没有在loser字典中，则将其加入到未输过任何比赛的玩家列表中。对于输掉一场比赛的分类，只会查看loser字典中输掉恰好一场比赛的玩家。因此，一个玩家即使赢过比赛，只要他在loser字典中输掉恰好一场，仍然会被加入到输掉一场比赛的列表中。

使用set而不是Counter来收集所有的winner可以有效避免重复并且减少不必要的信息存储。因为在这个特定问题中，我们只关心每个玩家是否赢过比赛，而不关心他们赢了多少场比赛。set自然提供了元素唯一性的保证，这对于识别未输过比赛的玩家来说是足够的。如果使用Counter，虽然也能实现相同的功能，但会额外记录每位玩家赢的次数，这在本题中是不必要的信息。