Easy

题目描述

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。

请你返回在矩阵主对角线上的所有元素和副对角线上且不在主对角线上元素的和。

示例 1：

输入：mat = [[1,2,3],
            [4,5,6],
            [7,8,9]]
输出：25
解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25
请注意，元素 mat[1][1] = 5 只会被计算一次。

示例 2：

输入：mat = [[1,1,1,1],
            [1,1,1,1],
            [1,1,1,1],
            [1,1,1,1]]
输出：8

示例 3：

输入：mat = [[5]]
输出：5

提示：

  • n == mat.length == mat[i].length
  • 1 <= n <= 100
  • 1 <= mat[i][j] <= 100

注意： 当且仅当矩阵的长度为奇数时，主对角线和副对角线才会有重叠元素，重叠位置在矩阵的中心。

解题思路

解题思路

这道题要求计算矩阵对角线元素的和，需要考虑主对角线和副对角线的情况。

思路分析

  1. 主对角线：从左上角到右下角的对角线，元素位置为 (i, i)，其中 i 从 0 到 n-1

  2. 副对角线：从右上角到左下角的对角线，元素位置为 (i, n-1-i)，其中 i 从 0 到 n-1

  3. 重复计算问题：当矩阵大小为奇数时，两条对角线会在中心点 (n/2, n/2) 重叠，需要避免重复计算

解决方案

方法一：一次遍历法（推荐）

  • 遍历矩阵的每一行，同时累加主对角线和副对角线的元素
  • 当 i != n-1-i 时（即不是中心点），两个对角线元素都加入总和
  • 当 i == n-1-i 时（即中心点），只加一次避免重复

方法二：分别计算再减去重复

  • 先计算主对角线的和
  • 再计算副对角线的和
  • 如果矩阵大小为奇数，减去中心点的值（因为被计算了两次）

两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(1)，这里给出更简洁的方法一。

代码实现

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size();
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            sum += mat[i][i]; // 主对角线
            sum += mat[i][n - 1 - i]; // 副对角线
        }
        
        // 如果矩阵大小为奇数，减去重复计算的中心元素
        if (n % 2 == 1) {
            sum -= mat[n / 2][n / 2];
        }
        
        return sum;
    }
};

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        total = 0
        
        for i in range(n):
            total += mat[i][i]  # 主对角线
            total += mat[i][n - 1 - i]  # 副对角线
        
        # 如果矩阵大小为奇数，减去重复计算的中心元素
        if n % 2 == 1:
            total -= mat[n // 2][n // 2]
        
        return total

public class Solution {
    public int DiagonalSum(int[][] mat) {
        int n = mat.Length;
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            sum += mat[i][i]; // 主对角线
            sum += mat[i][n - 1 - i]; // 副对角线
        }
        
        // 如果矩阵大小为奇数，减去重复计算的中心元素
        if (n % 2 == 1) {
            sum -= mat[n / 2][n / 2];
        }
        
        return sum;
    }
}

var diagonalSum = function(mat) {
    let sum = 0;
    let n = mat.length;
    
    for (let i = 0; i < n; i++) {
        sum += mat[i][i];
        sum += mat[i][n - 1 - i];
    }
    
    if (n % 2 === 1) {
        sum -= mat[Math.floor(n / 2)][Math.floor(n / 2)];
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历矩阵的 n 行，每行访问两个对角线元素
空间复杂度O(1)只使用了常数级别的额外空间存储变量

相关题目