目錄
什么是下三角矩陣？
我們要存哪些元素？一共幾個？
推導索引映射公式?
核心問題：給定 (i,j)，如何計算 k？
什么是下三角矩陣？
一個 n × n 的矩陣，如果它在主對角線以上的所有元素都是 0，那么它就是一個下三角矩陣。
比如 4×4 的矩陣：
[ a00 0 0 0 ]
[ a10 a11 0 0 ]
[ a20 a21 a22 0 ]
[ a30 a31 a32 a33 ]
我們發現：
-
只有 行號 ≥ 列號（即 i ≥ j）的位置有非零元素。
-
其他地方（即 i < j）全是 0，不需要存！
一個矩陣 A?是一個二維的數字表格。對于一個 n×n 的矩陣來說：
-
它一共有 n 行，每行 n?個元素。
-
每個元素用兩個下標表示：
A[i][j]，其中 i?是行號，j?是列號。
在 C 或 C++ 中我們常寫成：A[i][j]
我們要存哪些元素？一共幾個？
我們只存矩陣下三角區域的元素（含對角線），也就是：
-
第1行：只存1個元素（A??）
-
第2行：存2個元素（A??，A??）
-
第3行：存3個元素（A??，A??，A??）
-
...
-
第n行：存n個元素（A??，...，A??）
所以總共要存的元素個數是：1 + 2 + 3 + ... + n = n * (n + 1) / 2 個元素
推導索引映射公式?
假設我們用一維數組 a[k] 來存下三角矩陣的非零值，用行主順序（row-major order）存儲。
設矩陣是 n × n，下標從 1開始，那么我們就要構造一個下標轉換公式：
你給我 i, j（i ≥ j），我要算出它在數組 a[] 里的位置
我們按行來存：先存第1行，再第2行，再第3行……
例子（n=4）中，存儲順序是：
a[0] = A[1][1] ?
a[1] = A[2][1] ?
a[2] = A[2][2] ?
a[3] = A[3][1] ?
a[4] = A[3][2] ?
a[5] = A[3][3] ?
...
核心問題：給定 (i,j)，如何計算 k？
我們想要的 k 是：
第1行：有 1 個元素（j 從 1 到 1） ?
第2行：有 2 個元素（j 從 1 到 2） ?
... ?
第(i-1)行：有 (i - 1) 個元素 ?
=> 總共 (1 + 2 + ... + (i-1)) = (i-1) * i / 2?個元素
加上當前這一行中第 j 個元素（從左往右第 j 個）
所以： ?k = 前 (i - 1) 行的元素個數 + 第 j 列在當前行中的偏移量(j - 1)
? 最終公式：k = (i - 1) * i / 2 + (j - 1)
注意：這里的 k 是數組 a[k] 中的下標（從0開始）
?? 重要說明
-
這個公式只適用于 i ≥ j（也就是下三角部分）
-
如果你輸入了 i < j，就說明這個元素是 0，不在數組中！
?列主順序存儲：（這里不再詳細說明）
??示例驗證
矩陣如下（n=4）：
1 0 0 0
2 3 0 0
4 5 6 0
7 8 9 10
我們來看 A[4][2] 是多少：
-
i = 4, j = 2
-
index = (4 - 1) * 4 / 2 + (2 - 1) = 3 * 4 / 2 + 1 = 6 + 1 = 7
-
a[7] = A[4][2] = 8?
