LeetCode in Swift - 2924. Find Champion II （中文解釋）

題目

• https://leetcode.com/problems/find-champion-ii/description/
• https://leetcode.cn/problems/find-champion-ii/description/ （中文）

資料結構

• Graph
• Tree

題意

給一個數值 n ，帶表有一系列從 0 到 n - 1 的隊伍。以及一個 edges 陣列代表各隊的強弱關係。

這個強弱關係是一個 DAG (Directed Acyclic Graph, 有向無環圖) ，意味著從任意點出發，無法透過任何邊回到該點。詳見 維基百科 。

也就是當隊伍 0 比 1 強時，比 1 還弱的隊伍只會比 0 ，不會比 0 強。

找出冠軍

當一個隊伍沒有任何隊伍比他強時，就可以視為冠軍。以圖學的角度來說，就是 尋找這個 DAG 的所有根節點 (root nodes) 。

回傳

當冠軍只有唯一的一隊時，回傳該隊，否則回傳 -1 。

Routine

知道提議和該解決什麼問題後，就來制定 routine 。

準備初始資料集

根據 n 建立一個 set ，預設所有隊伍都是冠軍。

Routine - 走訪 edges

因為條件是「沒有比較強的隊伍」就可以視為冠軍，所以每一次走訪時，只要在「弱隊」的那個位置就可以從 set 中剔除，

回傳

走訪完成後，當 set 中只有一個隊伍時，就可以回傳該隊伍。否則回傳 -1 ；完成處理。

程式碼

class Solution {
    func findChampion(_ n: Int, _ edges: [[Int]]) -> Int {
        // 1. 準備資料及，預設大家都是冠軍
        var champions = Set(0..<n)

        // 2. Routine - 移除輸家
        for edge in edges {
            champions.remove(edge[1])
        }

        // 3. 根據題目條件回傳結果
        return champions.count == 1 ? champions.removeFirst() : -1
    }
}

複雜度分析

如題目的限制，令邊數為 m

• 時間複雜度： O(n + m)
  • 備註： Swift 中 Set 的 remove, removeFirst 的複雜度皆為 O(1) ，因為內部為類 dictionary 實作。
• 空間複雜度： O(n)
  • 冠軍列表，長度為 n

結語

以上，如果有什麼回饋，歡迎在留言區跟我說，謝謝！