3898. 统计每个顶点的度

题目描述

给你一个大小为 n x n 的二维整数数组 matrix，以邻接矩阵形式表示一个 无向图。该图包含 n 个顶点，编号从 0 到 n - 1。

matrix[i][j] = 1 表示顶点 i 与顶点 j 之间存在一条边。
matrix[i][j] = 0 表示顶点 i 与顶点 j 之间不存在边。

顶点的 度（degree）定义为与该顶点相连的边的数量。

请返回一个长度为 n 的整数数组 ans，其中 ans[i] 表示顶点 i 的度。

示例 1：

输入： matrix = [[0,1,1],[1,0,1],[1,1,0]]

输出： [2,2,2]

解释：

顶点 0 与顶点 1 和 2 相连，因此其度为 2。
顶点 1 与顶点 0 和 2 相连，因此其度为 2。
顶点 2 与顶点 0 和 1 相连，因此其度为 2。

因此，答案为 [2, 2, 2]。

示例 2：

输入： matrix = [[0,1,0],[1,0,0],[0,0,0]]

输出： [1,1,0]

解释：

顶点 0 与顶点 1 相连，因此其度为 1。
顶点 1 与顶点 0 相连，因此其度为 1。
顶点 2 没有与任何顶点相连，因此其度为 0。

因此，答案为 [1, 1, 0]。

示例 3：

输入： matrix = [[0]]

输出： [0]

解释：

图中只有一个顶点，且没有任何边与其相连，因此答案为 [0]。

提示：

1 <= n == matrix.length == matrix[i].length <= 100
matrix[i][i] == 0
matrix[i][j] 仅为 0 或 1
matrix[i][j] == matrix[j][i]

解法

方法一：模拟

我们可以直接模拟计算每个顶点的度。

对于每个顶点 \(i\)，我们遍历其对应的行 \(\text{matrix}[i]\)，统计其中值为 1 的元素的数量，即为顶点 \(i\) 的度。

时间复杂度 \(O(n^2)\)，其中 \(n\) 是图中顶点的数量。忽略答案数组的空间消耗，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def findDegrees(self, matrix: list[list[int]]) -> list[int]:
        ans = [0] * len(matrix)
        for i, row in enumerate(matrix):
            for x in row:
                ans[i] += x
        return ans

class Solution {
    public int[] findDegrees(int[][] matrix) {
        int n = matrix.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            for (int x : matrix[i]) {
                ans[i] += x;
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> findDegrees(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            for (int x : matrix[i]) {
                ans[i] += x;
            }
        }
        return ans;
    }
};

func findDegrees(matrix [][]int) []int {
    ans := make([]int, len(matrix))
    for i, row := range matrix {
        for _, x := range row {
            ans[i] += x
        }
    }
    return ans
}

function findDegrees(matrix: number[][]): number[] {
    const n = matrix.length;
    const ans: number[] = Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        for (const x of matrix[i]) {
            ans[i] += x;
        }
    }
    return ans;
}

3898. 统计每个顶点的度

题目描述

解法

方法一：模拟

评论