介绍

稀疏数组（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列的二维数组，每一列有固定含义，第一行是矩阵元信息，后续每行是一个有效元素的信息：

例子

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

原矩阵：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. 返回稀疏数组。

代码实现：

/**
 * 二维数组转稀疏数组
 * @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. 返回还原后的二维数组。

代码实现：

/**
 * 稀疏数组转二维数组（还原）
 * @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;
}

测试代码：验证压缩和还原的正确性

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完全一致，这里直接给出完整的压缩+还原代码，附带测试：

# 二维数组转稀疏数组
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）的实现，或者想了解稀疏数组的进阶用法（如结合链表实现），可以补充说明，我会继续细化～

原文出处：/show_1GW2h7TEQtw1.html