2359-找到离给定两个节点最近的节点

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i
没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离
较大值最小化 。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

示例 1：

**输入：** edges = [2,2,3,-1], node1 = 0, node2 = 1
**输出：** 2
**解释：** 从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。

示例 2：

**输入：** edges = [1,2,-1], node1 = 0, node2 = 2
**输出：** 2
**解释：** 节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。

提示：

  • n == edges.length
  • 2 <= n <= 105
  • -1 <= edges[i] < n
  • edges[i] != i
  • 0 <= node1, node2 < n

本题 视频讲解 已出炉，包含思考题的讲解，欢迎点赞三连，在评论区分享你对这场周赛的看法~

求出 node}_1 到每个点的距离 d_1 和 node}_2 到每个点的距离 d_2（无法到达时设为一个比较大的数），然后遍历 d_1 和 d_2，答案即为 \max(d_1[i],d_2[i]) 的最小值所对应的 i。若没有这样的节点，答案为 -1。

这可以用 BFS 来做，但由于题目的输入是内向基环树（森林），每个连通块至多有一个环，利用这一特性，代码实现时可以用一个简单的循环求出距离数组。

如果读者不了解内向基环树，我之前在 2127. 参加会议的最多员工数 的题解中作了详细介绍，可以参考。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n, min_dis, ans = len(edges), len(edges), -1
        def calc_dis(x: int) -> List[int]:
            dis = [n] * n
            d = 0
            while x >= 0 and dis[x] == n:
                dis[x] = d
                d += 1
                x = edges[x]
            return dis
        for i, d in enumerate(map(max, zip(calc_dis(node1), calc_dis(node2)))):
            if d < min_dis:
                min_dis, ans = d, i
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int[] d1 = calcDis(edges, node1), d2 = calcDis(edges, node2);
        int ans = -1, n = edges.length;
        for (int i = 0, minDis = n; i < n; ++i) {
            var d = Math.max(d1[i], d2[i]);
            if (d < minDis) {
                minDis = d;
                ans = i;
            }
        }
        return ans;
    }

    int[] calcDis(int[] edges, int x) {
        var n = edges.length;
        var dis = new int[n];
        Arrays.fill(dis, n);
        for (var d = 0; x >= 0 && dis[x] == n; x = edges[x])
            dis[x] = d++;
        return dis;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int closestMeetingNode(vector<int> &edges, int node1, int node2) {
        int n = edges.size(), min_dis = n, ans = -1;
        auto calc_dis = [&](int x) -> vector<int> {
            vector<int> dis(n, n);
            for (int d = 0; x >= 0 && dis[x] == n; x = edges[x])
                dis[x] = d++;
            return dis;
        };
        auto d1 = calc_dis(node1), d2 = calc_dis(node2);
        for (int i = 0; i < n; ++i) {
            int d = max(d1[i], d2[i]);
            if (d < min_dis) {
                min_dis = d;
                ans = i;
            }
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func closestMeetingNode(edges []int, node1, node2 int) int {
	n := len(edges)
	calcDis := func(x int) []int {
		dis := make([]int, n)
		for i := range dis {
			dis[i] = n
		}
		for d := 0; x >= 0 && dis[x] == n; x = edges[x] {
			dis[x] = d
			d++
		}
		return dis
	}

	d1 := calcDis(node1)
	d2 := calcDis(node2)
	minDis, ans := n, -1
	for i, d := range d1 {
		if d2[i] > d {
			d = d2[i]
		}
		if d < minDis {
			minDis, ans = d, i
		}
	}
	return ans
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 edges 的长度。
  • 空间复杂度：O(n)。

思考题

  1. 如果输入的不止两个节点 node}_1 和 node}_2，而是一个很长的 nodes 列表，要怎么做呢？
  2. 如果输入的是 queries 询问数组，每个询问包含两个节点 node}_1 和 node}_2，要你回答 closestMeetingNode(edges, node1, node2) 的答案，要怎么做呢？

解答见 视频讲解 。

 Comments
On this page
2359-找到离给定两个节点最近的节点