边积分最高的节点
难度:
标签:
题目描述
给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。
图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的 有向 边。
节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的 编号 总和。
返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。
示例 1：
输入：edges = [1,0,0,0,0,7,7,5] 输出：7 解释： - 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。 - 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。 - 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。 - 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。 节点 7 的边积分最高，所以返回 7 。
示例 2：
输入：edges = [2,0,0,2] 输出：0 解释： - 节点 1 和 2 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 = 3 。 - 节点 0 和 3 都有指向节点 2 的边，节点 2 的边积分等于 0 + 3 = 3 。 节点 0 和 2 的边积分都是 3 。由于节点 0 的编号更小，返回 0 。
提示：
n == edges.length2 <= n <= 1050 <= edges[i] < nedges[i] != i
代码结果
运行时间: 130 ms, 内存: 27.3 MB
/*
* 思路：
* 1. 使用 Java Stream 来计算每个节点的边积分。
* 2. 利用 IntStream 遍历节点并计算边积分。
* 3. 使用 Collectors.groupingBy 收集节点的边积分并求和。
* 4. 找出边积分最高的节点，如果有多个节点边积分相同则返回编号最小的那个。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int edgeScore(int[] edges) {
Map<Integer, Long> scores = IntStream.range(0, edges.length)
.boxed()
.collect(Collectors.groupingBy(i -> edges[i], Collectors.summingLong(i -> (long) i)));
return scores.entrySet().stream()
.max(Comparator.<Map.Entry<Integer, Long>>comparingLong(Map.Entry::getValue)
.thenComparing(Map.Entry::getKey, Comparator.reverseOrder()))
.get()
.getKey();
}
}解释
方法:
题解从每个节点的出边出发，计算所有指向每个节点的边的源节点编号总和，即边积分。使用一个数组score来记录每个节点的边积分，其中score[i]保存了所有指向节点i的源节点编号的总和。遍历一遍edges数组，对于每个节点i，找到它指向的节点to，然后将i累加到score[to]中。最后，使用max函数找出具有最大边积分的节点，并通过index函数获取其索引，即为所求的节点。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中提到，每个节点恰有一条出边。在这种情况下，是否可能存在一个节点没有任何入边？如果存在，该节点的边积分如何处理？
▷🦆
解题思路中使用了数组来累加指向每个节点的源节点编号，这种方法是否考虑了所有的边界情况，例如数组的索引是否可能超出边界？
▷🦆
在计算边积分时，题解提到使用max函数来找出最大边积分，但如果有多个节点边积分相同怎么办？题解中是否保证返回的是编号最小的节点？
▷🦆
题解提到在遍历edges数组时，对每个节点i，找到它指向的节点to，并将i累加到score[to]中。这种累加操作在所有编程语言中都是原子操作吗？如果不是，是否需要考虑并发安全问题？
▷