基本陣列操作 對角線之和 Matrix Diagonal Sum_Leetcode #1572

Rui Matayoshi on Unsplash

這題的題目在這裡:Matrix Diagonal Sum

題目敘述

題目會給我們一個方陣，要求我們計算兩條對角線的元素總和。

測試範例

Example 1:

Input: mat = [[1,2,3],
              [4,5,6],
              [7,8,9]]
Output: 25
Explanation: Diagonals sum: 1 + 5 + 9 + 3 + 7 = 25
Notice that element mat[1][1] = 5 is counted only once.

Example 2:

Input: mat = [[1,1,1,1],
              [1,1,1,1],
              [1,1,1,1],
              [1,1,1,1]]
Output: 8

Example 3:

Input: mat = [[5]]
Output: 5

約束條件

Constraints:

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

演算法

主對角線mat[i][i] 和

次要對角線mat[n-1-i][i]依序相加即可。

唯一的小細節要特別留意，當方陣的邊長n為奇數時，中心點的元素會被多計算一次，要記得扣掉。

程式碼

class Solution:
　def diagonalSum(self, mat: List[List[int]]) -> int:
　　
　　# edge length of square matrix: n x n
　　n = len(mat)

　　summation = 0
　　for i in range(n) :
　　　
　　　# primary diagnol
　　　summation += mat[i][i]

　　　# secondary diagnol
　　　summation += mat[n-1-i][i]

　　# When n is odd,
　　# avoid repeated computation on central element
　　if n % 2 == 1:
　　　summation -= mat[n//2][n//2]

　　return summation

複雜度分析

時間複雜度: O(n)

線性掃描，掃過主對角線和次對角線，總共耗時O(n)

空間複雜度: O(1)

所用到的都是固定尺寸的臨時變數，為常數級別O(1)

關鍵知識點

主對角線mat[i][i] 和

次要對角線mat[n-1-i][i]依序相加即可。

小細節要留意，當方陣的邊長n為奇數時，中心點的元素會被多計算一次，要記得扣掉。

這種相對簡單的題目，比的就是細心和穩定度!

Reference:

[1] Python/JS/Java/Go/C++ O(n) by iteration [w/ Comment] - Matrix Diagonal Sum - LeetCode