LeetCode 题解工作台
找到冠军 II
一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。每支队伍也是 有向无环图（DAG） 上的一个节点。 给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [u i , v i ] 表示图中存在一条从 u i 队到…
1
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图
答案摘要
根据题目描述，我们只需要统计每个节点的入度，记录在数组 中。如果只有一个节点的入度为 ，那么这个节点就是冠军，否则不存在唯一的冠军。 时间复杂度 ，空间复杂度 。其中 是节点的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图 题型思路
题目描述
一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。每支队伍也是 有向无环图（DAG） 上的一个节点。
给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [ui, vi] 表示图中存在一条从 ui 队到 vi 队的有向边。
从 a 队到 b 队的有向边意味着 a 队比 b 队 强 ，也就是 b 队比 a 队 弱 。
在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。
如果这场比赛存在 唯一 一个冠军，则返回将会成为冠军的队伍。否则，返回 -1 。
注意
- 环 是形如
a1, a2, ..., an, an+1的一个序列，且满足：节点a1与节点an+1是同一个节点；节点a1, a2, ..., an互不相同；对于范围[1, n]中的每个i，均存在一条从节点ai到节点ai+1的有向边。 - 有向无环图 是不存在任何环的有向图。
示例 1：
输入：n = 3, edges = [[0,1],[1,2]] 输出：0 解释：1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。
示例 2：
输入：n = 4, edges = [[0,2],[1,3],[1,2]] 输出：-1 解释：2 队比 0 队和 1 队弱。3 队比 1 队弱。但是 1 队和 0 队之间不存在强弱对比。所以答案是 -1 。
提示：
1 <= n <= 100m == edges.length0 <= m <= n * (n - 1) / 2edges[i].length == 20 <= edge[i][j] <= n - 1edges[i][0] != edges[i][1]- 生成的输入满足：如果
a队比b队强，就不存在b队比a队强 - 生成的输入满足：如果
a队比b队强，b队比c队强，那么a队比c队强
解题思路
方法一：统计入度
根据题目描述，我们只需要统计每个节点的入度，记录在数组 中。如果只有一个节点的入度为 ，那么这个节点就是冠军，否则不存在唯一的冠军。
时间复杂度 ，空间复杂度 。其中 是节点的数量。
class Solution:
def findChampion(self, n: int, edges: List[List[int]]) -> int:
indeg = [0] * n
for _, v in edges:
indeg[v] += 1
return -1 if indeg.count(0) != 1 else indeg.index(0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N + M) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Expect clear reasoning on why only zero in-degree nodes qualify as champions.
- question_mark
Watch for handling multiple zero in-degree teams and returning -1 correctly.
- question_mark
Check that candidate selection does not exceed linear time relative to nodes and edges.
常见陷阱
外企场景- error
Forgetting that multiple zero in-degree teams mean no unique champion.
- error
Assuming the node with the largest index or edge count is the champion.
- error
Ignoring edge cases with empty edge lists where any team could be champion.
进阶变体
外企场景- arrow_right_alt
Finding the weakest team by identifying nodes with zero out-degree instead of zero in-degree.
- arrow_right_alt
Handling weighted edges to determine dominance when strengths are quantified.
- arrow_right_alt
Detecting cycles in the input graph which would invalidate the DAG assumption.