🏗️ 第 1 週：資料結構基礎（Data Structures） 4/150
04. 稀疏數組的轉換思路 - 如何將龐大的「0」壓縮成一個小巧的數據結構？
一、 核心思路：只記錄「不一樣」的事物
要將一個龐大的二維陣列（2D Array）轉換成稀疏數組（Sparse Array），我們的目標非常明確：拋棄所有的 0（預設值），只保留關鍵數據。
這個轉換過程可以拆解為標準的三步曲：
1. 統計（Count）： 遍歷原始陣列，算出到底有幾個「有效數據」（非 0 數據）。2. 建表（Create）： 根據有效數據的數量，創建一個新的「瘦身版」陣列。
3. 填充（Fill）： 將有效數據的座標（列、行）和數值填入新表。
二、 轉換實戰：二維陣列 ➡️ 稀疏數組（壓縮）
假設我們有一個 6*7 的棋盤，上面只有兩顆棋子：
· 第 0 列，第 3 行有一顆黑子（值為 22）
· 第 1 列，第 2 行有一顆藍子（值為 15）
· 其他全是 0。
步驟 1：建立格式
稀疏數組固定只有 3 個欄位（Column），分別代表：
[列 Row, 行 Col, 值 Value]
步驟 2：決定大小
我們需要多少列（Row）來存這些資料？
· 第 1 列（檔頭 Header）： 用來記錄原始棋盤的規模（共有幾列、幾行、幾個有效值）。這是為了還原時做準備。
· 後續列（數據 Data）： 每一個有效數據佔用一列。
所以，稀疏數組的大小 = (有效數據個數 + 1) × 3。
在這個例子中，有 2 個數據，所以大小是 3 × 3。
步驟 3：填充數據
我們來看看轉換後的樣子：
這樣，原本需要 6*7=42 個格子的空間，現在只需要 3*3 = 9 個格子。壓縮完成！
三、 還原實戰：稀疏數組 ➡️ 二維陣列（解壓縮）
當我們讀取存檔，要恢復棋盤畫面時，就需要逆向操作。這也是為什麼「檔頭」如此重要。
1. 讀取檔頭（第一行）：
o 讀取稀疏數組的第 0 行 [6, 7, 2]。
o 電腦就知道了：「喔！我要先準備一個 $6 \times 7$ 的空陣列，預設全部填 0。」
2. 回填數據（後續行）：
o 讀取第 1 行 [0, 3, 22] ➡️ 把新陣列的 Arr[0][3] 設為 22。
o 讀取第 2 行 [1, 2, 15] ➡️ 把新陣列的 Arr[1][2] 設為 15。
3. 完成：
o 剩下的格子因為沒動過，自然保持為 0。棋盤完美重現！
四、 工程師的思考筆記（Implementation Logic）
在寫程式（如 Java, Python, C++）實作這個功能時，要特別注意以下邏輯順序：
1. 千萬別急著建陣列：
你必須先跑一次迴圈（Loop）計算 sum（有效數據個數），否則你不知道稀疏數組該開多大。
o 註：在 Python 等動態語言中可以用 List 動態增加，但在 C/Java 中必須先定義大小。
2. 座標的紀錄：
轉換時，記錄的是「原始陣列」的座標。
還原時，是依照記錄的座標去「指定賦值」。
3. 邊界條件：
如果原始陣列全是 0，稀疏數組應該至少有一行（檔頭），記錄 [6, 7, 0]。
五、 總結
• 轉換是為了儲存與傳輸：用最小的代價保留核心資訊。
• 還原是為了顯示與運算：將壓縮的數據恢復成人類或演算法好處理的矩陣形式。
• 檔頭（Header）是關鍵：沒有第一行的「全域資訊」，後面的數據就是無頭蒼蠅，無法還原回正確的維度。
