稀疏数组-马育民老师

# 介绍

**稀疏数组（Sparse Array）**是编程中专门用来 **压缩存储稀疏矩阵** 的一种数据结构，核心解决“大部分元素为默认值（如0）、少数元素有效”的矩阵占用内存过大、存储冗余的问题。

# 稀疏矩阵

稀疏矩阵是指**矩阵中有效元素（非默认值）的数量远少于总元素数量**的矩阵（行业内一般认为有效元素占比＜5%）。

比如一个10行8列的矩阵，只有3个非0元素，其余都是0，这就是典型的稀疏矩阵：

```
0 0 0 0 0 0 0 0
0 5 0 0 0 0 0 0
0 0 0 0 9 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 7 0
```
如果直接用二维数组存储这个矩阵，需要存储`10*8=80`个元素，但实际只有3个有效元素，剩下77个都是无意义的0，这就是**存储冗余**，稀疏数组就是为了解决这个问题。

### 原理

稀疏数组的本质是**用一个小规模的二维数组**，只存储稀疏矩阵的**有效元素信息**，抛弃所有默认值，从而大幅节省内存。

#### 稀疏数组的固定结构

稀疏数组是一个`(有效元素数+1)行 × 3列`的二维数组，每一列有固定含义，第一行是**矩阵元信息**，后续每行是**一个有效元素的信息**：

| 行号 | 列0 | 列1 | 列2 |
|------|-----|-----|-----|
| 0    | 原矩阵的总行数 | 原矩阵的总列数 | 原矩阵的有效元素数 |
| 1    | 有效元素1的行坐标 | 有效元素1的列坐标 | 有效元素1的值 |
| 2    | 有效元素2的行坐标 | 有效元素2的列坐标 | 有效元素2的值 |
| ...  | ... | ... | ... |
| n    | 有效元素n的行坐标 | 有效元素n的列坐标 | 有效元素n的值 |

### 例子

将上面的稀疏矩阵转稀疏数组

原矩阵：10行、8列、3个有效元素
有效元素位置&值：(1,1)=5、(2,4)=9、(9,6)=7
对应的稀疏数组：
```
10  8  3
1   1  5
2   4  9
9   6  7
```
原本需要存储80个元素，现在只需要存储`3+1=4`行×3列=12个元素，内存占用大幅减少，这就是稀疏数组的核心价值。

### 应用场景

稀疏数组是**空间换时间**的反例（**时间换空间**），牺牲少量遍历的时间，换取大幅的内存节省，主要用在**有效元素少、矩阵规模大**的场景：

1. **棋盘类游戏的存档/读档**：如五子棋、象棋，棋盘大部分位置为空（0），只有少数棋子（有效元素），用稀疏数组存储棋盘状态，存档文件体积极小；
2. **大数据矩阵处理**：如机器学习、数值分析中的稀疏矩阵（如用户-商品评分矩阵，大部分用户未评分，值为0）；
3. **图形学/地理信息**：如地图的高程矩阵，大部分区域高程相同，只有少数区域有变化；
4. **数据库/文件存储**：存储大规模稀疏数据时，用稀疏数组压缩后写入文件/数据库，减少IO和存储成本。

# 操作

稀疏数组的使用围绕两个核心操作展开，也是面试/编程中最常考的点，这里用**Java实现**（最易理解，其他语言如Python/C逻辑完全一致），附带详细注释。

### 操作1：普通二维数组 → 稀疏数组（压缩）

**实现步骤**：

1. 遍历原二维数组，统计**有效元素的数量count**；
2. 创建稀疏数组`sparseArr = new int[count+1][3]`；
3. 稀疏数组第一行赋值：`sparseArr[0][0] = 原行数`、`sparseArr[0][1] = 原列数`、`sparseArr[0][2] = count`；
4. 再次遍历原二维数组，将有效元素的**行、列、值**依次存入稀疏数组的后续行；
5. 返回稀疏数组。

**代码实现**：
```java
/**
 * 二维数组转稀疏数组
 * @param arr 原二维数组（默认默认值为0）
 * @return 转换后的稀疏数组
 */
public static int[][] toSparseArray(int[][] arr) {
    // 步骤1：统计有效元素数量
    int count = 0;
    int rows = arr.length; // 原数组行数
    if (rows == 0) return new int[0][3]; // 空数组直接返回
    int cols = arr[0].length; // 原数组列数

for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (arr[i][j] != 0) { // 有效元素（非0）
                count++;
            }
        }
    }

// 步骤2：创建稀疏数组
    int[][] sparseArr = new int[count + 1][3];
    // 步骤3：赋值稀疏数组第一行（元信息）
    sparseArr[0][0] = rows;
    sparseArr[0][1] = cols;
    sparseArr[0][2] = count;

// 步骤4：赋值有效元素信息
    int index = 1; // 稀疏数组的行索引，从1开始（0行是元信息）
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (arr[i][j] != 0) {
                sparseArr[index][0] = i; // 有效元素行坐标
                sparseArr[index][1] = j; // 有效元素列坐标
                sparseArr[index][2] = arr[i][j]; // 有效元素值
                index++;
            }
        }
    }
    return sparseArr;
}
```

### 操作2：稀疏数组 → 普通二维数组（还原）

**实现步骤**：

1. 从稀疏数组第一行获取原矩阵的**总行数rows**、**总列数cols**，创建原二维数组`originalArr = new int[rows][cols]`（默认值为0，正好匹配稀疏矩阵的默认值）；
2. 遍历稀疏数组的后续行（从第1行到最后一行）；
3. 依次取出每行的**行坐标i**、**列坐标j**、**值val**，赋值给原数组：`originalArr[i][j] = val`；
4. 返回还原后的二维数组。

**代码实现**：
```java
/**
 * 稀疏数组转二维数组（还原）
 * @param sparseArr 稀疏数组
 * @return 还原后的原二维数组
 */
public static int[][] toOriginalArray(int[][] sparseArr) {
    // 步骤1：判断稀疏数组是否有效
    if (sparseArr == null || sparseArr.length == 0) {
        return new int[0][0];
    }
    // 从稀疏数组第一行获取原矩阵的行、列
    int rows = sparseArr[0][0];
    int cols = sparseArr[0][1];
    int[][] originalArr = new int[rows][cols]; // 初始化，默认值为0

// 步骤2：遍历稀疏数组，赋值有效元素
    for (int i = 1; i < sparseArr.length; i++) {
        int x = sparseArr[i][0]; // 有效元素行坐标
        int y = sparseArr[i][1]; // 有效元素列坐标
        int val = sparseArr[i][2]; // 有效元素值
        originalArr[x][y] = val;
    }
    return originalArr;
}
```

### 测试代码：验证压缩和还原的正确性
```java
public static void main(String[] args) {
    // 1. 创建一个测试用的稀疏矩阵（10行8列）
    int[][] original = new int[10][8];
    original[1][1] = 5;
    original[2][4] = 9;
    original[9][6] = 7;
    System.out.println("原二维数组：");
    for (int[] row : original) {
        for (int num : row) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

// 2. 转稀疏数组
    int[][] sparse = toSparseArray(original);
    System.out.println("\n转换后的稀疏数组：");
    for (int[] row : sparse) {
        for (int num : row) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

// 3. 稀疏数组还原为二维数组
    int[][] restore = toOriginalArray(sparse);
    System.out.println("\n还原后的二维数组：");
    for (int[] row : restore) {
        for (int num : row) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
```
**输出结果**：还原后的数组和原数组完全一致，说明压缩和还原操作正确。

# Python版实现（更简洁，适合快速开发）
如果用Python实现，语法更简洁，核心逻辑和Java完全一致，这里直接给出完整的压缩+还原代码，附带测试：
```python
# 二维数组转稀疏数组
def to_sparse_array(arr):
    if not arr:
        return []
    rows = len(arr)
    cols = len(arr[0])
    count = 0
    # 统计有效元素
    for i in range(rows):
        for j in range(cols):
            if arr[i][j] != 0:
                count += 1
    # 创建稀疏数组
    sparse_arr = [[rows, cols, count]]
    # 赋值有效元素
    for i in range(rows):
        for j in range(cols):
            if arr[i][j] != 0:
                sparse_arr.append([i, j, arr[i][j]])
    return sparse_arr

# 稀疏数组转二维数组
def to_original_array(sparse_arr):
    if not sparse_arr:
        return []
    rows, cols, _ = sparse_arr[0]
    original_arr = [[0 for _ in range(cols)] for _ in range(rows)]
    # 赋值有效元素
    for i in range(1, len(sparse_arr)):
        x, y, val = sparse_arr[i]
        original_arr[x][y] = val
    return original_arr

# 测试
if __name__ == "__main__":
    # 原稀疏矩阵
    original = [[0]*8 for _ in range(10)]
    original[1][1] = 5
    original[2][4] = 9
    original[9][6] = 7
    print("原数组：")
    for row in original:
        print(row)
    
    # 压缩
    sparse = to_sparse_array(original)
    print("\n稀疏数组：")
    for row in sparse:
        print(row)
    
    # 还原
    restore = to_original_array(sparse)
    print("\n还原后的数组：")
    for row in restore:
        print(row)
```

# 注意事项

1. **适用场景有限**：如果矩阵的有效元素占比高（如＞50%），用稀疏数组会**适得其反**（需要额外存储行、列坐标，占用更多内存），此时直接用普通二维数组即可；
2. **默认值可自定义**：本文默认默认值为0，实际开发中可根据需求改为其他值（如null、-1），只需修改遍历判断条件（如`arr[i][j] != null`）；
3. **多维扩展**：本文讲的是二维稀疏数组，实际可扩展到三维/高维稀疏数组，核心逻辑不变，只是增加坐标列数（如三维稀疏数组为`count+1行 × 4列`，列含义：总行、总列、总高、有效元素数，后续行存储x、y、z、值）。

# 总结
1. 稀疏数组是**压缩存储稀疏矩阵**的工具，核心解决**存储冗余**问题，本质是`(有效元素数+1)行×3列`的二维数组；
2. 两个核心操作：**普通二维数组→稀疏数组（压缩）**、**稀疏数组→普通二维数组（还原）**，所有语言逻辑一致，核心是统计有效元素+记录坐标和值；
3. 适用**有效元素少、矩阵规模大**的场景（如棋盘存档、稀疏矩阵处理），是编程中**时间换空间**的典型应用。

如果需要某一种特定语言（如C/C++/JavaScript）的实现，或者想了解稀疏数组的进阶用法（如结合链表实现），可以补充说明，我会继续细化～

原文出处：http://malaoshi.top/show_1GW2h7TEQtw1.html