力扣每日一题——找到离给定两个节点最近的节点

目录

题目链接：2359. 找到离给定两个节点最近的节点 - 力扣（LeetCode）

题目描述

解法一：双指针路径交汇法​

基本思路

关键步骤

为什么这样可行呢我请问了？

举个例子

特殊情况

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

总结

---

题目链接：2359. 找到离给定两个节点最近的节点 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你一个 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

---

解法一：双指针路径交汇法​

        这道题目的核心是在一个有向图中，每个节点最多只有一条出边，可能存在环。给定两个起点 node1 和 node2，要找一个节点 x，使得两个起点都能到达 x，并且两个起点到 x 的距离中较大的那个值尽可能小。如果多个节点满足条件，选编号最小的；如果不存在，返回 -1。

基本思路

        因为每个节点最多只有一条出边，整个图的结构其实很简单：从任意节点出发，沿着出边走，要么走到尽头（遇到 -1），要么进入一个环然后开始循环。这种结构决定了从 node1 或 node2 出发的路径是唯一的，不会分叉，只是可能绕圈。

关键步骤

1. ​​分别计算两个起点能到达哪些节点​​
   用两个数组（比如 dist1 和 dist2）记录 node1 和 node2 到每个节点的距离。初始化时都设为 -1，表示不可达。然后从 node1 出发，沿着出边走，每走一步记录当前步数（距离），直到走到尽头或遇到已经访问过的节点（说明进入环了，再走会重复，此时停掉）。对 node2 同样操作一遍。

2. ​​处理环的干扰​​
   如果路径进入环，比如从 node1 走到节点 A 后开始绕圈，那么第一次走到 A 时的距离就是最短距离。之后再绕圈只会让距离变大，所以遇到访问过的节点直接停掉，避免死循环。

3. ​​找最优节点​​
   遍历所有节点，如果一个节点在 dist1 和 dist2 中都有记录（说明两个起点都能到达它），就计算 max(dist1[i], dist2[i])（即两个距离的较大值）。我们需要的正是这个较大值最小的节点。如果有多个节点值相同，选编号最小的那个。

为什么这样可行呢我请问了？

• ​​路径唯一性​​：因为每个节点最多一条出边，从起点出发的路径是唯一的，不会分叉，所以记录的距离就是最短距离。
• ​​环的处理​​：遇到环就停，保证了第一次到达节点的距离是最小的，后续绕圈只会增加距离，不用考虑。
• ​​最优解筛选​​：直接比较所有公共节点的距离较大值，取最小值，符合题目要求。

举个例子

假设图是 edges = [2, 2, 3, -1]，node1=0，node2=1：

• node1（0）的路径：0 → 2 → 3，距离 dist1[2]=1，dist1[3]=2。
• node2（1）的路径：1 → 2 → 3，距离 dist2[2]=1，dist2[3]=2。
  公共节点是 2 和 3。节点 2 的较大值是 max(1,1)=1，节点 3 是 max(2,2)=2，所以选节点 2。

特殊情况

        如果两个起点没有公共可达节点（比如一个走到尽头，另一个进环但路径不重合），直接返回 -1。

---

Java写法：

class Solution {public int closestMeetingNode(int[] edges, int node1, int node2) {int n = edges.length;int[] dist1 = new int[n];int[] dist2 = new int[n];Arrays.fill(dist1, -1);Arrays.fill(dist2, -1);// 计算 node1 到各节点的距离int cur = node1, steps = 0;while (cur != -1 && dist1[cur] == -1) {dist1[cur] = steps++;cur = edges[cur];}// 计算 node2 到各节点的距离cur = node2;steps = 0;while (cur != -1 && dist2[cur] == -1) {dist2[cur] = steps++;cur = edges[cur];}// 寻找最优节点int minMaxDist = Integer.MAX_VALUE;int ans = -1;for (int i = 0; i < n; i++) {if (dist1[i] != -1 && dist2[i] != -1) {int maxDist = Math.max(dist1[i], dist2[i]);if (maxDist < minMaxDist || (maxDist == minMaxDist && i < ans)) {minMaxDist = maxDist;ans = i;}}}return ans;}
}

C++写法：

#include <vector>
#include <climits>
#include <algorithm>
using namespace std;class Solution {
public:int closestMeetingNode(vector<int>& edges, int node1, int node2) {int n = edges.size();vector<int> dist1(n, -1);vector<int> dist2(n, -1);// 计算 node1 到各节点的距离int cur = node1, steps = 0;while (cur != -1 && dist1[cur] == -1) {dist1[cur] = steps++;cur = edges[cur];}// 计算 node2 到各节点的距离cur = node2;steps = 0;while (cur != -1 && dist2[cur] == -1) {dist2[cur] = steps++;cur = edges[cur];}// 寻找最优节点int minMaxDist = INT_MAX;int ans = -1;for (int i = 0; i < n; i++) {if (dist1[i] != -1 && dist2[i] != -1) {int maxDist = max(dist1[i], dist2[i]);if (maxDist < minMaxDist || (maxDist == minMaxDist && i < ans)) {minMaxDist = maxDist;ans = i;}}}return ans;}
};

运行时间

时间复杂度和空间复杂度

时间复杂度：O(n)​

空间复杂度：O(n)​​​

---

---

---

总结

​​问题核心​​：给定一个有向图（节点最多一条出边，可能存在环），需找到节点 node1 和 node2 均可达的节点，使两者到该节点距离的​​较大值最小化​​。若有多个解，返回最小节点编号；无解则返回 -1。

​​解法精髓​​：采用 ​​双指针路径交汇法​​（Dual-Pointer Path Convergence）