You are given a directed graph with n
nodes labeled from 0
to n - 1
, where each node has exactly one outgoing edge.
The graph is represented by a given 0-indexed integer array edges
of length n
, where edges[i]
indicates that there is a directed edge from node i
to node edges[i]
.
The edge score of a node i
is defined as the sum of the labels of all the nodes that have an edge pointing to i
.
Return the node with the highest edge score. If multiple nodes have the same edge score, return the node with the smallest index.
Example 1:
Input: edges = [1,0,0,0,0,7,7,5] Output: 7 Explanation: - The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10. - The node 0 has an edge pointing to node 1. The edge score of node 1 is 0. - The node 7 has an edge pointing to node 5. The edge score of node 5 is 7. - The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11. Node 7 has the highest edge score so return 7.
Example 2:
Input: edges = [2,0,0,2] Output: 0 Explanation: - The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3. - The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3. Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.
Constraints:
n == edges.length
2 <= n <= 105
0 <= edges[i] < n
edges[i] != i
边积分最高的节点。
给你一个有向图,图中有 n 个节点,节点编号从 0 到 n - 1 ,其中每个节点都 恰有一条 出边。
图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示,其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的 有向 边。
节点 i 的 边积分 定义为:所有存在一条指向节点 i 的边的节点的 编号 总和。
返回 边积分 最高的节点。如果多个节点的 边积分 相同,返回编号 最小 的那个。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/node-with-highest-edge-score
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目以数组的形式给了一些点的联通关系,但是这道题跟图论毫无关系,就是一道数组题。
我们创建一个和 edges 等长的数组记录每个 node 的得分。对于 input 数组,下标 i 代表的是一条有向边的起点,i 位置上的值代表的是这条有向边的终点。对于每个节点,他的边积分等于能到达此节点的所有的边的起点的和。比如第一个例子,有多条边指向 0,那么 0 的边积分就等于所有指向 0 的节点的 index 的和。这里我展示一下分别用hashmap和数组实现的代码,速度差距还是挺大的。注意由于节点的个数会大到 10^5,所以记录每个节点的变积分需要用 long 型。
时间O(n)
空间O(n)
hashmap实现
1 class Solution { 2 public int edgeScore(int[] edges) { 3 HashMap<Integer, Long> map = new HashMap<>(); 4 int len = edges.length; 5 for (int i = 0; i < edges.length; i++) { 6 int from = i; 7 int to = edges[i]; 8 if (!map.containsKey(to)) { 9 map.put(to, 0L); 10 } 11 long sum = map.getOrDefault(to, 0L); 12 map.put(to, sum + from); 13 } 14 15 long max = 0; 16 int res = 0; 17 for (int i = 0; i < len; i++) { 18 if (map.containsKey(i)) { 19 long val = map.get(i); 20 if (val > max) { 21 res = i; 22 max = val; 23 } 24 } 25 } 26 return res; 27 } 28 }
数组实现
1 class Solution { 2 public int edgeScore(int[] edges) { 3 long[] map = new long[edges.length]; 4 for (int i = 0; i < edges.length; i++) { 5 int from = i; 6 int to = edges[i]; 7 map[to] += from; 8 } 9 10 int res = 0; 11 long max = 0L; 12 for (int i = 0; i < map.length; i++) { 13 if (map[i] > max) { 14 max = map[i]; 15 res = i; 16 } 17 } 18 return res; 19 } 20 }
标签:Node,node,score,int,Score,edges,edge,Edge,节点 From: https://www.cnblogs.com/cnoodle/p/16585444.html