題目描述:
給定一個 n × n 的正方形矩陣 mat,計算其主對角線和副對角線上所有元素的總和。如果某個元素同時在兩條對角線上(即矩陣中心元素,僅當 n 為奇數時),只計算一次。
解題思路: 遍歷矩陣的每一行 i:
mat[i][i]mat[i][n-1-i]將兩者都加入總和。當 n 為奇數時,中心位置 i == n-1-i,此時同一元素被加了兩次,需要在最後減去一次。
時間複雜度:O(n) — 只需遍歷一次矩陣的 n 行,每行做常數操作。
空間複雜度:O(1) — 只使用常數額外空間。
1. Let n = number of rows in mat 2. Initialize sum = 0 3. For each row i from 0 to n-1: a. sum += mat[i][i] (primary diagonal) b. sum += mat[i][n-1-i] (secondary diagonal) 4. If n is odd: a. sum -= mat[n/2][n/2] (remove double-counted center) 5. Return sum
條件判斷法 O(n):在迴圈中檢查 i != n-1-i 再決定是否加副對角線元素,避免事後減去中心。邏輯稍微複雜但省去最後的判斷。
雙重迴圈遍歷 O(n²):遍歷整個矩陣,對每個元素檢查是否在對角線上。時間複雜度較差,不建議使用。