Medium

题目描述

给你一个有向图，图中有 n 个节点，节点标号从 0 到 n - 1，其中每个节点都恰有一条出边。

图由一个给定的长度为 n 的 0 索引 整数数组 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⁵
  • 0 <= edges[i] < n
  • edges[i] != i

解题思路

这是一道图论中计算节点入边权重和的问题。我们需要理解"边分数"的定义：对于节点 i，它的边分数是所有指向它的节点标号之和。

解题思路：

  1. 理解题意：每个节点 i 都有一条出边指向 edges[i]，我们要计算每个节点的入边节点标号总和。

  2. 统计入边：遍历 edges 数组，对于每个节点 i，它有一条边指向 edges[i]，因此 edges[i] 的边分数要加上 i。

  3. 寻找最大值：维护一个数组记录每个节点的边分数，然后找到边分数最大的节点。如果有多个节点边分数相同，选择标号最小的。

  4. 注意事项：由于节点数可达 10⁵，边分数可能很大，需要使用 64 位整数避免溢出。

算法步骤：

  • 创建一个数组 scores 记录每个节点的边分数
  • 遍历 edges，对于节点 i 指向的节点 edges[i]，将 i 加到 scores[edges[i]] 中
  • 遍历 scores 找到最大分数对应的最小标号节点

时间复杂度 O(n)，空间复杂度 O(n)，是最优解法。

代码实现

class Solution {
public:
    int edgeScore(vector<int>& edges) {
        int n = edges.size();
        vector<long long> scores(n, 0);
        
        // 计算每个节点的边分数
        for (int i = 0; i < n; i++) {
            scores[edges[i]] += i;
        }
        
        // 找到边分数最高的节点，相同时返回标号最小的
        int result = 0;
        for (int i = 1; i < n; i++) {
            if (scores[i] > scores[result]) {
                result = i;
            }
        }
        
        return result;
    }
};

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        n = len(edges)
        scores = [0] * n
        
        # 计算每个节点的边分数
        for i, target in enumerate(edges):
            scores[target] += i
        
        # 找到边分数最高的节点，相同时返回标号最小的
        result = 0
        for i in range(1, n):
            if scores[i] > scores[result]:
                result = i
        
        return result

public class Solution {
    public int EdgeScore(int[] edges) {
        int n = edges.Length;
        long[] scores = new long[n];
        
        // 计算每个节点的边分数
        for (int i = 0; i < n; i++) {
            scores[edges[i]] += i;
        }
        
        // 找到边分数最高的节点，相同时返回标号最小的
        int result = 0;
        for (int i = 1; i < n; i++) {
            if (scores[i] > scores[result]) {
                result = i;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} edges
 * @return {number}
 */
var edgeScore = function(edges) {
    const n = edges.length;
    const scores = new Array(n).fill(0);
    
    // 计算每个节点的边分数
    for (let i = 0; i < n; i++) {
        scores[edges[i]] += i;
    }
    
    // 找到边分数最高的节点，相同时返回标号最小的
    let result = 0;
    for (let i = 1; i < n; i++) {
        if (scores[i] > scores[result]) {
            result = i;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历edges数组一次计算边分数，再遍历scores数组一次找最大值
空间复杂度O(n)需要额外的scores数组存储每个节点的边分数

相关题目