1572. 矩阵对角线元素的和

难度: 简单

来源: 每日一题 2023.08.11

---

给你一个正方形矩阵 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

class Solution {
    public int diagonalSum(int[][] mat) {

    }
}

分析与题解

---

• 重拳出击👊🏻 + 找规律 + 一半遍历法

  简单题我又是一次重拳出击👊🏻👊🏻👊🏻, 首先一个非常关键的条件就是该矩阵是一个 正方形矩阵 , 正方形矩阵在对称性上更加具有优势和规律.

  在正方形中对角线,会有如下的规律, 在i行上, 必然有 mat[i][i] 与 mat[i][length - 1 - i] 在对角线上.

  同时由于上下对称的原因, 也必然有 mat[length - 1 - i][i] 与 mat[length - 1 - i][length - 1 - i] 也在对角线上, 就是因为这个上下对称的缘故, 我们可以减少一半的遍历, 降低我们的时间复杂度.

  具体逻辑代码如下所示.

  for(int i = 0; i < length/2; i++) {
      sum += mat[i][i];
      sum += mat[i][length - 1 - i];
      sum += mat[length - 1 - i][i];
      sum += mat[length - 1 - i][length - 1 - i];
  }
  

  同时, 我们也要考虑正方形矩阵是奇数行还是偶数行,如果是奇数行, 我们需要单独把中心一点加上.

  if(length%2 == 1) {
      sum += mat[length/2][length/2];
  }
  

  整个题目的题解过程如下所示.

  class Solution {
      public int diagonalSum(int[][] mat) {
          // 正方形矩阵必然对称,我们只需要遍历一半即可, 中间一行单独处理
          int sum = 0, length = mat.length;
          // 遍历一半即可
          for(int i = 0; i < length/2; i++) {
              sum += mat[i][i];
              sum += mat[i][length - 1 - i];
              sum += mat[length - 1 - i][i];
              sum += mat[length - 1 - i][length - 1 - i];
          }
          // 中间一行单独处理, 也是对[[5]] 单个元素的处理
          if(length%2 == 1) {
              sum += mat[length/2][length/2];
          }
          return sum;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n/2), 一半遍历循环, 时间复杂度与矩阵数组的长度相关.
  • 空间复杂度: O(1), 常量级别的空间复杂度.

  结果如下所示.