3898. 求每个顶点的度数

Easy

题目描述

给你一个大小为 n x n 的二维整数数组 matrix，表示一个有 n 个顶点的无向图的邻接矩阵，顶点标号从 0 到 n - 1。

• matrix[i][j] = 1 表示顶点 i 和 j 之间有一条边。
• matrix[i][j] = 0 表示顶点 i 和 j 之间没有边。

顶点的度数是连接到该顶点的边的数量。

返回一个大小为 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 的度数是矩阵中第 i 行的和

解题思路

解题思路

这道题考查的是图论中顶点度数的基本概念。在无向图的邻接矩阵表示中，顶点的度数等于该顶点对应行（或列）中 1 的个数。

核心思路：

1. 对于顶点 i，其度数就是 matrix[i] 这一行中所有元素的和
2. 由于是无向图，邻接矩阵是对称的，即 matrix[i][j] == matrix[j][i]
3. 主对角线上的元素都是 0（顶点不与自己相连）

解法分析：

• 方法一（推荐）： 直接遍历每一行，计算行和。时间复杂度 O(n²)，空间复杂度 O(1)
• 方法二： 遍历上三角矩阵，同时更新对应的两个顶点度数。时间复杂度 O(n²)，但实际运行时间约为方法一的一半

由于题目规模较小（n ≤ 100），两种方法性能差异不大，推荐使用方法一，代码更简洁直观。

实现要点：

• 利用语言内置的求和函数可以让代码更简洁
• 注意返回数组的初始化和大小

代码实现

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

class Solution:
    def findDegrees(self, matrix: list[list[int]]) -> list[int]:
        return [sum(row) for row in matrix]

public class Solution {
    public int[] FindDegrees(int[][] matrix) {
        int n = matrix.Length;
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i] += matrix[i][j];
            }
        }
        
        return result;
    }
}

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var findDegrees = function(matrix) {
    return matrix.map(row => row.reduce((sum, val) => sum + val, 0));
};

复杂度分析

说明：

• 时间复杂度：需要遍历整个 n×n 的邻接矩阵
• 空间复杂度：除了存储结果的数组外，只使用常数额外空间