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

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

给你一个 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 <= 10⁵
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int closestMeetingNode(vector<int>& edges, int node1, int node2) { } };

golang 解法, 执行用时: 128 ms, 内存消耗: 10 MB, 提交时间: 2023-09-14 01:14:26

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
}

cpp 解法, 执行用时: 136 ms, 内存消耗: 95.4 MB, 提交时间: 2023-09-14 01:14:10

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;
    }
};

java 解法, 执行用时: 8 ms, 内存消耗: 54.6 MB, 提交时间: 2023-09-14 01:13:59

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;
    }
}

python3 解法, 执行用时: 228 ms, 内存消耗: 29.7 MB, 提交时间: 2023-09-14 01:13:46

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

上一题

下一题

详情