边积分最高的节点

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你一个有向图，图中有 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.length
• 2 <= n <= 10^5
• 0 <= edges[i] < n
• edges[i] != i

思路分析

首先我们应该要先读懂题意，知道题目要求我们做什么。题目会给我们一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。我们需要统计每个节点的边积分，那么在这里的边积分是怎么定义的呢？题目的定义是这样的：所有存在一条指向节点 i 的边的节点的 编号 总和。所以我们可以使用一个hash表来记录每一个节点的边积分，只需要遍历每一个节点，将其出边的节点积分加上当前节点的编号，找出其中边积分最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。

• 1、使用hash表记录每个节点边积分

let map = {},max = 0,res = 0;

• 2、遍历计算边积分

for(let i = 0; i < edges.length; i++){
    map[edges[i]] = (map[edges[i]] || 0) + i;
    ……
}

• 3、更新边积分最高的节点

if(map[edges[i]] > max){
    max = map[edges[i]];
    res = edges[i];
}else if(map[edges[i]] == max){
    if(res > edges[i]){
        res = edges[i];
    }
}

完整代码如下：

AC代码

/**
 * @param {number[]} edges
 * @return {number}
 */
 var edgeScore = function(edges) {
     let map = {},max = 0,res = 0;
     for(let i = 0; i < edges.length; i++){
         map[edges[i]] = (map[edges[i]] || 0) + i;
         if(map[edges[i]] > max){
             max = map[edges[i]];
             res = edges[i];
         }else if(map[edges[i]] == max){
             if(res > edges[i]){
                 res = edges[i];
             }
         }
     }
     return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。