(LeetCode 每日一题)2359. 找到离给定两个节点最近的节点( 图)

题目：2359. 找到离给定两个节点最近的节点

思路：分别记录node1和node2到其他节点的距离d1、d2，然后找最小的值即可。时间复杂度0(n)，细节看注释。

C++版本：

class Solution {
public:
	// 因为最多只会有一条出边，所以直接循环来遍历即可
    void solve(vector<int>& edges,int u,vector<int>& d){
        int dis=0;
        // 因为有环的存在，所以要判断是否是第一次遍历
        while(u>=0&&d[u]==INT_MAX){
            d[u]=dis;
            dis++;
            u=edges[u];
        }
    }

    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n=edges.size();
        // d1、d2分别记录node1和node2到其他节点的距离
        vector<int> d1(n+1,INT_MAX),d2(n+1,INT_MAX);
        solve(edges,node1,d1);
        solve(edges,node2,d2);
        // 维护最小值、及对应的下标id
        int mn=INT_MAX,id=-1;
        for(int i=0;i<=n;i++){
            int t=max(d1[i],d2[i]);
            if(mn>t){
                mn=t;
                id=i;
            }
        }
        return id;
    }
};

JAVA版本：

class Solution {

    void solve(int[] edges,int u,int[] d){
        int dis=0;
        while(u>=0&&d[u]==Integer.MAX_VALUE){
            d[u]=dis;
            dis++;
            u=edges[u];
        }
    }
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n=edges.length;
        int[] d1=new int[n+1];
        int[] d2=new int[n+1];
        Arrays.fill(d1,Integer.MAX_VALUE);
        Arrays.fill(d2,Integer.MAX_VALUE);

        solve(edges,node1,d1);
        solve(edges,node2,d2);
        int mn=Integer.MAX_VALUE;
        int id=-1;
        for(int i=0;i<=n;i++){
            int t=Math.max(d1[i],d2[i]);
            if(mn>t){
                mn=t;
                id=i;
            }
        }
        return id;
    }
}

Go版本：

func closestMeetingNode(edges []int, node1 int, node2 int) int {
    n:=len(edges)
    d1:=make([]int,n+1)
    d2:=make([]int,n+1)
    for i:=range d1 {
        d1[i]=math.MaxInt32
        d2[i]=math.MaxInt32
    }
    solve(edges,node1,d1)
    solve(edges,node2,d2)
    mn:=math.MaxInt32
    id:=-1
    for i:=0;i<=n;i++ {
        t:=max(d1[i],d2[i])
        if mn>t {
            mn=t
            id=i
        }
    }
    return id
}

func solve(edges []int,u int,d []int){
    dis:=0
    for u>=0 && d[u]==math.MaxInt32 {
        d[u]=dis
        dis++
        u=edges[u]
    }
}