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

小松鼠

發佈於演算法題目解析

更新於 2024/11/18發佈於 2023/11/19閱讀時間約 3 分鐘

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

留言

留言分享你的想法！

小松鼠的演算法樂園

95會員

427內容數

由有業界實戰經驗的演算法工程師，手把手教你建立解題的框架，一步步寫出高效、清晰易懂的解題答案。著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。

小松鼠的演算法樂園的其他內容

2024/10/06

🆚大小有別根據大小給予序號 Rank Transform of an Array_Leetcode #1331

題目敘述 Rank Transform of an Array 給定一個陣列arr，請根據數字的大小給予序號，序號值介於1~len( set(arr) )之間。最大的數字給予最大的序號。次大的數字給予次大的序號。 ...依此類推最小的數字給予最小的序號1。