什么是稀疏数组？它是如何压缩存储的？
简化版
当一个数组里绝大多数元素都是同一个值（通常是 0），只有少数是有效值时，它就是稀疏数组。直接存整个二维数组太浪费。压缩办法：只记录有效元素的「行、列、值」，再加一行头信息记「总行数、总列数、有效元素个数」。存棋盘、地图这类大量空白的场景特别省空间。
详细版
「稀疏」指有效数据占比极低。比如一个 11×11 的五子棋盘，只下了 2 个子，那就有 121 个格子、119 个是 0，直接存 int[11][11] 太浪费。
压缩思路：不存所有格子，只存「非零元素在哪、值是多少」。用一个「三列表」记录：
原始 11×11 棋盘，只有两个非零：(1,2)=1, (2,3)=2
压缩后（第一行是头，记录规模和有效个数）：
行 列 值
11 11 2 ← 头：总行数 总列数 有效元素个数
1 2 1 ← 第一个有效元素：行1 列2 值1
2 3 2 ← 第二个有效元素：行2 列3 值2原来要 121 个 int，现在只要 3 行 × 3 列 = 9 个 int，空间大幅下降。还原时先按头信息建一个全 0 的二维数组，再把后面每行的 (行,列,值) 填回去。
完整版教学
一、稀疏数组解决什么问题
稀疏数组不是一种「新结构」，而是一种压缩存储技巧。当二维数组里有效值极少、大量是重复的默认值（0 或空）时，逐格存储会浪费大量内存和磁盘。稀疏数组的核心思想是：既然大部分是 0，那就只记录不是 0 的那些，其余默认补 0。
二、压缩格式：三元组表
标准做法是用一张 k+1 行、3 列的表（k 为有效元素个数）：
- 第 0 行（头）：
总行数、总列数、有效元素个数。 - 第 1 ~ k 行：每个有效元素的
所在行、所在列、值。
这就是「三元组（row, col, value）」表示法。
三、压缩与还原的过程
压缩（二维 → 稀疏）：
- 遍历原二维数组，数出有多少个非 0 元素
sum。 - 建
sparse[sum+1][3]，第 0 行写入总行、总列、sum。 - 再遍历一遍，把每个非 0 元素的行、列、值依次填进后面各行。
还原（稀疏 → 二维）：
- 读第 0 行，按总行数、总列数建一个全 0 的二维数组。
- 读后面每一行，把
(行, 列)位置填上对应的值。
四、什么时候用、什么时候别用
- 适合：有效元素占比很低（比如 < 10%）。棋盘存盘、稀疏矩阵、地图数据、推荐系统里的用户-物品评分矩阵等。
- 不适合：数组本身就很密（大部分非 0）。这时三元组反而更占空间（每个元素要存 3 个数），得不偿失。
判断标准很简单：有效元素太少才压缩。密集数组硬压缩会「越压越大」。
五、和其他稀疏存储的关系
三元组表是最基础的稀疏表示。工程上处理稀疏矩阵还有更高效的格式，如 CSR（行压缩）、CSC（列压缩），它们在三元组基础上进一步压缩行/列索引，便于做矩阵运算，广泛用于科学计算和机器学习库（如 SciPy 的稀疏矩阵）。原理同源：都是「只存非零 + 记录位置」。
| 存储方式 | 记录内容 | 适合场景 |
|---|---|---|
| 原始二维数组 | 每个格子都存 | 数据密集、随机访问每个位置频繁 |
| 三元组表 | (row, col, value) 加头信息 | 教学、存盘、非零元素很少 |
| CSR | 非零值、列索引、行指针 | 按行遍历和矩阵运算 |
| CSC | 非零值、行索引、列指针 | 按列遍历和矩阵运算 |
数字例子：一个 10000 × 10000 的 int 矩阵有 1 亿个格子，原始存储约 400MB。如果只有 1000 个非零元素，三元组表约需要 (1000 + 1) * 3 个整数，约 12012 字节（不计对象额外开销），空间差距非常明显。
稀疏数组不是为了让单点访问更快，而是为了在非零元素很少时节省存储。压缩后要访问某个坐标，通常还需要在记录表里查找。
六、常见误区与追问
- 误区：只要有 0 就应该用稀疏数组。 只有默认值占绝大多数时才划算；数据较密时三元组会额外保存行列信息，可能更费空间。
- 误区：稀疏数组一定只能压缩 0。 本质是压缩“默认值”，默认值可以是 0、空白、无穷大等，取决于业务含义。
- 误区：压缩后还能 O(1) 访问任意坐标。 三元组表要查找对应
(row,col)记录，朴素查找是 O(k)，需要额外索引才能更快。 - 追问：三元组表第一行为什么要存总行数和总列数？ 还原二维数组时必须知道原矩阵形状，否则只知道非零位置不够。
- 追问：压缩和还原的复杂度是多少？ 压缩通常要扫描原矩阵 O(rows*cols)，还原要初始化矩阵并回填 k 个有效元素。
- 追问：CSR/CSC 和三元组有什么区别？ CSR/CSC 仍只存非零值，但把行或列索引进一步压缩，便于按行或按列做高效运算。
七、加强记忆
稀疏数组是「大部分是 0、少数有效值」时的压缩技巧：用三元组表只记录有效元素的 行、列、值，并在第一行写总行数、总列数、有效个数。压缩时遍历统计再填表，还原时先建全 0 数组再回填。只在有效元素占比极低时用；数组本身很密时压缩反而更费空间。进阶格式有 CSR/CSC。