寻找冠军 II

2924。寻找冠军 II

难度：中等

主题：图表

一场比赛中有n支球队，编号从0到n-1；每个团队也是DAG中的一个节点。

给定整数 n 和一个 0 索引 长度为 m 的二维整数数组边，表示 DAG，其中 >dges[i] = [u _i, v_i] 表示有来自团队的有向边u_i 到图表中的 v_i 团队。

图中从a到b的有向边意味着a队强比b队弱比a队

如果没有b队比a队更强，A队将成为锦标赛的冠军

如果有唯一冠军，则返回将成为锦标赛冠军的队伍，否则返回-1

笔记

• 循环 _{是一系列节点 a}1_{, a}2_{, ..., a}n_{, a}n 1 _{使得节点 a}1 _{与节点 a}1 _{是同一节点a}n 1_{，节点 a}1_{, a}2_{, ..., a}n _{是不同的，并且有一个有向对于范围 [1, n].}
• DAG 是一个没有任何周期的有向图。

示例1：

• 输入： n = 3，边 = [[0,1],[1,2]]
• 输出： 0
• 解释： 1队比0队弱，2队比1队弱，所以冠军是0队。

示例2：

• 输入： n = 4，边 = [[0,2],[1,3],[1,2]]
• 输出： -1
• 说明： 队伍 2 比队伍 0 和队伍 1 弱。队伍 3 比队伍 1 弱。但是队伍 1 和队伍 0 并不比其他队伍弱。所以答案是-1。

约束：

1 m == Edges.length
0 边[i].length == 2
0 边[i][0] != 边[i][1]
生成输入，如果a队强于b队，则b队不强于a队。
生成的输入使得如果a队强于b队并且b队强于c队，则a队强于c队。

提示：

1. 冠军在 DAG 中的入度应为 0。

解决方案：

我们需要在给定的有向无环图 (DAG) 中识别 入度 为 0 的团队。没有传入优势的球队代表着没有其他球队比他们更强大的球队，这使得他们成为冠军的候选者。如果恰好有一支球队的入度为0，那么它就是唯一的冠军。如果有多个或没有这样的团队，结果为-1。

让我们用 PHP 实现这个解决方案：2924。寻找冠军 II

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @return Integer
 */
function findChampion($n, $edges) {
    // Initialize in-degrees for all teams
    $inDegree = array_fill(0, $n, 0);

    // Calculate the in-degree for each team
    foreach ($edges as $edge) {
        $inDegree[$edge[1]]++;
    }

    // Find teams with in-degree 0
    $candidates = [];
    for ($i = 0; $i < $n; $i++) {
        if ($inDegree[$i] == 0) {
            $candidates[] = $i;
        }
    }

    // If exactly one team has in-degree 0, return it; otherwise, return -1
    return count($candidates) === 1 ? $candidates[0] : -1;
}

// Example 1
$n1 = 3;
$edges1 = [[0, 1], [1, 2]];
echo "Example 1 Output: " . findChampion($n1, $edges1) . PHP_EOL; // Output: 0

// Example 2
$n2 = 4;
$edges2 = [[0, 2], [1, 3], [1, 2]];
echo "Example 2 Output: " . findChampion($n2, $edges2) . PHP_EOL; // Output: -1
?>

解释：

1. 输入解析:

   • n 是团队数量。
   • Edges 是图中有向边的列表。

2. 初始化入度:

   • 创建一个大小为 n 的数组 inDegree，初始化为 0。

3. 计算入度:

   • 对于每条边 [u, v]，增加 v 的入度（v 队多一个入边）。

4. 寻找候选人：

   • 迭代 inDegree 数组并收集入度为 0 的索引。这些索引代表没有其他更强球队的球队。

5. 决出冠军：

   • 如果恰好有一支队伍的入度为0，则它​​是唯一的冠军。
   • 如果多个团队或没有团队的入度为 0，则返回 -1。

示例演练

示例1：

• 输入：n = 3，边 = [[0, 1], [1, 2]]
• 入度：[0, 1, 1]
• 入度为 0 的团队：[0]
• 输出：0（Team 0 是唯一的冠军）。

示例2：

• 输入：n = 4，边 = [[0, 2], [1, 3], [1, 2]]
• 入度：[0, 0, 2, 1]
• 入度为 0 的团队：[0, 1]
• 输出：-1（有多个潜在冠军）。

复杂性分析

1. 时间复杂度:

   • 计算入度：O(m)，其中 m 是边数。
   • 检查团队：O(n)，其中 n 是团队数量。
   • 总计：O(n·m)。

2. 空间复杂度:

   • inDegree 数组：O(n).

这个解决方案非常高效，并且在给定的约束条件下工作。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是寻找冠军 II的详细内容。更多信息请关注PHP中文网其他相关文章！