边积分最高的节点

2374. 边积分最高的节点

给你一个有向图，图中有 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⁵
0 <= edges[i] < n
edges[i] != i

原站题解

去查看

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

class Solution { public: int edgeScore(vector<int>& edges) { } };

python3 解法, 执行用时: 137 ms, 内存消耗: 28 MB, 提交时间: 2024-09-21 09:59:20

# 虽然简洁，但不是一次遍历
class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        score = [0] * len(edges)
        for i, to in enumerate(edges):
            score[to] += i
        return score.index(max(score))

cpp 解法, 执行用时: 142 ms, 内存消耗: 119.6 MB, 提交时间: 2024-09-21 09:58:53

class Solution {
public:
    int edgeScore(vector<int>& edges) {
        int n = edges.size(), ans = 0;
        vector<long long> score(n);
        for (int i = 0; i < n; i++) {
            int to = edges[i];
            score[to] += i;
            if (score[to] > score[ans] || score[to] == score[ans] && to < ans) {
                ans = to;
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 3 ms, 内存消耗: 56.7 MB, 提交时间: 2024-09-21 09:58:34

class Solution {
    public int edgeScore(int[] edges) {
        int ans = 0;
        long[] score = new long[edges.length];
        for (int i = 0; i < edges.length; i++) {
            int to = edges[i];
            score[to] += i;
            if (score[to] > score[ans] || score[to] == score[ans] && to < ans) {
                ans = to;
            }
        }
        return ans;
    }
}

rust 解法, 执行用时: 11 ms, 内存消耗: 4 MB, 提交时间: 2024-09-21 09:58:16

impl Solution {
    pub fn edge_score(edges: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut score = vec![0i64; edges.len()];
        for (i, &to) in edges.iter().enumerate() {
            let to = to as usize;
            score[to] += i as i64;
            if score[to] > score[ans] || score[to] == score[ans] && to < ans {
                ans = to;
            }
        }
        ans as _
    }
}

javascript 解法, 执行用时: 132 ms, 内存消耗: 59.5 MB, 提交时间: 2023-06-07 11:03:56

/**
 * @param {number[]} edges
 * @return {number}
 */
var edgeScore = function(edges) {
    let t = Array(edges.length).fill(0);
    for(let i = 0; i < edges.length; i++){
        t[edges[i]] += i 
    }
    let max = Math.max(...t)
    return t.findIndex(v => v == max)
};

golang 解法, 执行用时: 208 ms, 内存消耗: 9.2 MB, 提交时间: 2023-06-07 11:03:29

func edgeScore(edges []int) int {
    n := len(edges)
    scores := make([]int, n)
    for from, to := range edges {
        scores[to] += from
    }
    ans := 0
    for k,v := range scores{
        if v > scores[ans]{
            ans = k
        }
    }
    return ans
}

golang 解法, 执行用时: 148 ms, 内存消耗: 9.4 MB, 提交时间: 2023-06-07 11:03:07

func edgeScore(edges []int) (ans int) {
	score := make([]int, len(edges))
	for i, to := range edges {
		score[to] += i
		if score[to] > score[ans] || score[to] == score[ans] && to < ans {
			ans = to
		}
	}
	return
}

python3 解法, 执行用时: 200 ms, 内存消耗: 27.2 MB, 提交时间: 2023-06-07 11:02:47

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        ans, score = 0, [0] * len(edges)
        for i, to in enumerate(edges):
            score[to] += i
            if score[to] > score[ans] or score[to] == score[ans] and to < ans:
                ans = to
        return ans

上一题

下一题

详情