What is the main pattern used in Find Players With Zero or One Losses?

The main pattern is array scanning combined with a hash lookup to count losses efficiently.

How do I handle players who never lost any match?

Track all players in the hash map and assign zero losses by default for players not appearing as losers.

Do the output lists need to be sorted?

Yes, both lists must be returned in increasing order to match problem requirements.

Can this problem handle large numbers of matches?

Yes, using a hash map for loss counts ensures linear time scanning with reasonable space usage.

What common mistakes should I avoid?

Avoid missing zero-loss players, double-counting losses, and returning unsorted lists.

#2225

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个整数数组 matches 其中 matches[i] = [winner i , loser i ] 表示在一场比赛中 winner i 击败了 loser i 。返回一个长度为 2 的列表 answer ： answer[0] 是所有没有输掉任何比赛的玩家列表。 answer[1] …

数组哈希表排序计数

题目描述

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

返回一个长度为 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⁵
matches[i].length == 2
1 <= winner_i, loser_i <= 10⁵
winner_i != loser_i
所有 matches[i] 互不相同

lightbulb

解题思路

方法一：哈希表 + 排序

我们用一个哈希表 $\textit{cnt}$ 记录每个玩家输掉的比赛场次。

然后遍历哈希表，将输掉 $0$ 场比赛的玩家放入 $\textit{ans}[0]$ ，将输掉 $1$ 场比赛的玩家放入 $\textit{ans}[1]$ 。

最后将 $\textit{ans}[0]$ 和 $\textit{ans}[1]$ 按照升序排序，返回结果。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为比赛场次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	complexity is O(n + k log k) where n is the number of matches and k is the number of unique players, due to array scanning and sorting. Space complexity is O(k) for the hash map storing loss counts.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion on hash table versus array-only counting trade-offs.
question_mark
Watch for missed edge cases like players with no matches.
question_mark
Check if candidates sort results before returning to meet output order requirements.

warning

常见陷阱

外企场景

error
Failing to include players who never lost any match in the zero-loss list.
error
Incorrectly counting multiple losses for a player when matches list contains repeated winners or losers.
error
Returning unsorted lists which violates the increasing order requirement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find players with exactly k losses instead of zero or one.
arrow_right_alt
Return players grouped by total wins instead of losses.
arrow_right_alt
Handle cases with duplicate matches or missing players in the dataset.

help

常见问题

外企场景

继续练习

#2248 多个数组求交集 #1782 统计点对的数目 #1481 不同整数的最少数目