Description
給定一個正方形矩陣
mat，回傳主對角線和副對角線元素的總和。如果某個元素同時在兩條對角線上，只計算一次。
Example:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]] Output: 25 (1+5+9 + 3+5+7 = 30, 但 5 重複所以 30-5 = 25)
Intuition#
核心思路：遍歷每一行，加上主對角線
mat[i][i]和副對角線mat[i][n-1-i]的值，注意中心點不要重複計算。
- 主對角線元素：
mat[i][i] - 副對角線元素：
mat[i][n-1-i] - 若 n 為奇數，中心元素
mat[n/2][n/2]會被算兩次，需要減掉
Approaches#
⭐1: 單次遍歷#
- 概念: 遍歷每行加上兩條對角線的值，最後若 n 為奇數則減去中心元素
- 時間複雜度:
O(n)- 遍歷 n 行 - 空間複雜度:
O(1)
class Solution {
fun diagonalSum(mat: Array<IntArray>): Int {
val n = mat.size
var sum = 0
for (i in 0 until n) {
sum += mat[i][i] // 主對角線
sum += mat[i][n - 1 - i] // 副對角線
}
// 若 n 為奇數，中心元素被加了兩次
if (n % 2 == 1) {
sum -= mat[n / 2][n / 2]
}
return sum
}
}2: 條件判斷避免重複#
- 概念: 在迴圈中直接判斷是否為同一元素，避免最後的修正
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun diagonalSum(mat: Array<IntArray>): Int {
val n = mat.size
var sum = 0
for (i in 0 until n) {
sum += mat[i][i]
if (i != n - 1 - i) {
sum += mat[i][n - 1 - i]
}
}
return sum
}
}🔑 Takeaways#
- Pattern: 矩陣對角線遍歷——主對角線
[i][i]、副對角線[i][n-1-i] - 關鍵技巧: 奇數邊長矩陣的中心點是兩條對角線的交點，注意不要重複計算