2359. Find Closest Node to Given Two Nodes

Medium
Description

給定一個有向圖，每個節點最多有一條出邊，用 edges[i] 表示（-1 表示無出邊）。給定兩個節點 node1 和 node2，找一個節點使得 max(dist(node1, node), dist(node2, node)) 最小。若有多個答案，回傳編號最小的。

Example:

Input: edges = [2,2,3,-1], node1 = 0, node2 = 1 Output: 2

Intuition#

分別從 node1 和 node2 出發計算到所有可達節點的距離，找兩者都能到達且最大距離最小的節點。

  • 每個節點最多一條出邊，所以從任一節點出發的路徑是唯一的
  • 分別計算從 node1 和 node2 到所有節點的距離
  • 找出兩者都可達的節點中，max(d1, d2) 最小的

Approaches#

⭐1: 兩次距離計算#

  • 概念: 從 node1 和 node2 分別遍歷計算距離，然後遍歷所有節點找最佳答案
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val n = edges.size
        val dist1 = getDist(edges, node1, n)
        val dist2 = getDist(edges, node2, n)

        var minDist = Int.MAX_VALUE
        var result = -1

        for (i in 0 until n) {
            if (dist1[i] != -1 && dist2[i] != -1) {
                val maxD = maxOf(dist1[i], dist2[i])
                if (maxD < minDist) {
                    minDist = maxD
                    result = i
                }
            }
        }
        return result
    }

    private fun getDist(edges: IntArray, start: Int, n: Int): IntArray {
        val dist = IntArray(n) { -1 }
        var cur = start
        var d = 0
        while (cur != -1 && dist[cur] == -1) {
            dist[cur] = d
            d++
            cur = edges[cur]
        }
        return dist
    }
}

2: 相同邏輯的 BFS 寫法#

  • 概念: 用 BFS 風格遍歷計算距離
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
        val n = edges.size

        fun bfs(start: Int): IntArray {
            val dist = IntArray(n) { -1 }
            val queue = ArrayDeque<Int>()
            queue.add(start)
            dist[start] = 0
            while (queue.isNotEmpty()) {
                val cur = queue.removeFirst()
                val next = edges[cur]
                if (next != -1 && dist[next] == -1) {
                    dist[next] = dist[cur] + 1
                    queue.add(next)
                }
            }
            return dist
        }

        val dist1 = bfs(node1)
        val dist2 = bfs(node2)

        var minDist = Int.MAX_VALUE
        var result = -1
        for (i in 0 until n) {
            if (dist1[i] != -1 && dist2[i] != -1) {
                val maxD = maxOf(dist1[i], dist2[i])
                if (maxD < minDist) {
                    minDist = maxD
                    result = i
                }
            }
        }
        return result
    }
}

🔑 Takeaways#

  • Pattern: 雙源最短路 – 分別計算兩個起點到所有節點的距離
  • 關鍵技巧: 每個節點最多一條出邊使得遍歷為 O(n)；用 dist[cur] == -1 判斷是否已訪問可偵測環