尋找冠軍 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 _與節點a1 _{是同一節點a}n 1_，節點a1_{, 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中文網其他相關文章！