找到离给定两个节点最近的节点
难度:
标签:
题目描述
给你一个 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
代码结果
运行时间: 64 ms, 内存: 27.8 MB
/*
题目思路:
1. 使用广度优先搜索计算从node1和node2到其他节点的最短距离。
2. 使用Java Stream来处理节点的距离和找到最小的最大距离节点。
3. 如果没有满足条件的节点,返回-1。
*/
import java.util.*;
import java.util.stream.IntStream;
public class Solution {
public int findClosestMeetingNode(int[] edges, int node1, int node2) {
int n = edges.length;
int[] dist1 = bfs(edges, node1);
int[] dist2 = bfs(edges, node2);
return IntStream.range(0, n)
.filter(i -> dist1[i] < Integer.MAX_VALUE && dist2[i] < Integer.MAX_VALUE)
.mapToObj(i -> new int[]{i, Math.max(dist1[i], dist2[i])})
.min(Comparator.<int[]>comparingInt(a -> a[1]).thenComparingInt(a -> a[0]))
.map(a -> a[0])
.orElse(-1);
}
private int[] bfs(int[] edges, int start) {
int n = edges.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
dist[start] = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
int neighbor = edges[node];
if (neighbor != -1 && dist[neighbor] == Integer.MAX_VALUE) {
dist[neighbor] = dist[node] + 1;
queue.offer(neighbor);
}
}
return dist;
}
}
解释
方法:
该题解采用的是同时从两个节点开始追踪路径的策略。首先,创建两个布尔数组flag_1和flag_2来标记从node1和node2出发访问过的节点。接着,从两个节点同时开始沿着有向图的边走,直到两者相遇或到达终点。过程中检查对方是否已经访问过当前节点,若是,则返回当前节点,因为这意味着找到了一个共同可达节点。如果在某一步中,一个节点无法再前进(即该节点没有出边或到达了先前访问过的节点),则停止并返回-1,表示不存在这样的节点。这种方法利用了双指针的思想,同时追踪两个节点的路径,直到它们相遇。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中使用的同时追踪两个节点路径的策略,该策略是否考虑了图中可能存在的环形结构对算法的影响?
▷🦆
为什么题解在两个节点都不能前进时直接返回-1?是否有可能存在其他未被考虑到的节点作为合适的最近共同节点?
▷🦆
题解中提到,如果节点已经被对方访问过则可判断为共同可达节点,这种方法在有向图中是否总是有效?
▷🦆
题解假设了每个节点至多有一条出边,这个假设是否限制了算法的通用性?如果图中允许节点有多条出边,该如何调整算法?
▷