稀疏数组 | 小菜鸟

稀疏数组（Sparse Array）：高效压缩稀疏数据的优化方案

稀疏数组是一种针对大部分元素为默认值（如 0、null） 的二维数组设计的压缩存储结构，通过仅记录有效元素的位置和值，大幅减少存储空间和数据传输开销。本文详细解析稀疏数组的原理、转换流程、应用场景及实现代码。

稀疏数组的核心概念

适用场景

当一个二维数组中：

绝大多数元素是默认值（如 0、空值）；
仅有少量元素具有实际意义（如 1、2 等非默认值）。

此时直接存储原始数组会造成大量空间浪费，而稀疏数组通过 “保留有效信息，舍弃默认值” 实现压缩。

核心思想

稀疏数组不存储默认值，仅记录：

原始数组的总行数、总列数；
所有非默认值元素的位置（行号、列号）和值。

原始数组与稀疏数组的转换

以五子棋棋盘为例（11×11 的二维数组，0 表示空位，1 表示黑子，2 表示白子），演示转换过程。

原始数组（11×11）

int[][] chessBoard = new int[11][11];
chessBoard[1][2] = 1; // 第1行第2列放黑子
chessBoard[2][3] = 2; // 第2行第3列放白子

原始数组中，121 个元素里仅有 2 个有效值，其余均为 0，空间利用率极低。

转换为稀疏数组的步骤

步骤 1：统计有效元素个数

遍历原始数组，记录非 0 元素的数量（记为count）。
本例中count = 2。

步骤 2：构建稀疏数组结构

稀疏数组是一个(count + 1) × 3的二维数组，其中：

第 0 行：存储原始数组的元信息
sparse[0][0] = 原始数组行数（11）
sparse[0][1] = 原始数组列数（11）
sparse[0][2] = 有效元素个数（2）
第 1 至 count 行：存储每个有效元素的信息
sparse[i][0] = 元素行号
sparse[i][1] = 元素列号
sparse[i][2] = 元素值

步骤 3：填充稀疏数组

将原始数组中的有效元素依次填入稀疏数组：

稀疏数组（3行3列）：
[11, 11, 2]  →  元信息：11行、11列、2个有效元素
[1, 2, 1]    →  第1行第2列的值为1（黑子）
[2, 3, 2]    →  第2行第3列的值为2（白子）

从稀疏数组还原原始数组

步骤 1：创建空的原始数组

根据稀疏数组第 0 行的元信息，初始化一个rows × cols的二维数组：

int rows = sparse[0][0];   // 11
int cols = sparse[0][1];   // 11
int[][] restored = new int[rows][cols];

步骤 2：填充有效元素

遍历稀疏数组第 1 至 count 行，将每个元素的行号、列号和值还原到原始数组：

for (int i = 1; i < sparse.length; i++) {
    int row = sparse[i][0];   // 行号
    int col = sparse[i][1];   // 列号
    int val = sparse[i][2];   // 值
    restored[row][col] = val;
}

代码实现（Java）

public class SparseArrayDemo {
    public static void main(String[] args) {
        // 1. 创建原始二维数组（11×11 五子棋棋盘）
        int[][] original = new int[11][11];
        original[1][2] = 1; // 黑子
        original[2][3] = 2; // 白子

        // 打印原始数组
        System.out.println("原始数组：");
        for (int[] row : original) {
            for (int val : row) {
                System.out.printf("%d\t", val);
            }
            System.out.println();
        }

        // 2. 统计有效元素个数
        int count = 0;
        for (int i = 0; i < original.length; i++) {
            for (int j = 0; j < original[i].length; j++) {
                if (original[i][j] != 0) {
                    count++;
                }
            }
        }

        // 3. 构建稀疏数组
        int[][] sparse = new int[count + 1][3];
        sparse[0][0] = original.length;       // 总行数
        sparse[0][1] = original[0].length;    // 总列数
        sparse[0][2] = count;                 // 有效元素个数

        // 填充有效元素
        int index = 1; // 从第1行开始记录有效元素
        for (int i = 0; i < original.length; i++) {
            for (int j = 0; j < original[i].length; j++) {
                if (original[i][j] != 0) {
                    sparse[index][0] = i;
                    sparse[index][1] = j;
                    sparse[index][2] = original[i][j];
                    index++;
                }
            }
        }

        // 打印稀疏数组
        System.out.println("\n稀疏数组：");
        for (int[] row : sparse) {
            System.out.printf("%d\t%d\t%d\n", row[0], row[1], row[2]);
        }

        // 4. 从稀疏数组还原原始数组
        int rows = sparse[0][0];
        int cols = sparse[0][1];
        int[][] restored = new int[rows][cols];

        for (int i = 1; i < sparse.length; i++) {
            int row = sparse[i][0];
            int col = sparse[i][1];
            int val = sparse[i][2];
            restored[row][col] = val;
        }

        // 打印还原后的数组
        System.out.println("\n还原后的数组：");
        for (int[] row : restored) {
            for (int val : row) {
                System.out.printf("%d\t", val);
            }
            System.out.println();
        }
    }
}

输出结果：

原始数组：
0    0    0    0    0    0    0    0    0    0    0    
0    0    1    0    0    0    0    0    0    0    0    
0    0    0    2    0    0    0    0    0    0    0    
...（其余行均为0）

稀疏数组：
11    11    2
1    2    1
2    3    2

还原后的数组：
0    0    0    0    0    0    0    0    0    0    0    
0    0    1    0    0    0    0    0    0    0    0    
0    0    0    2    0    0    0    0    0    0    0    
...（与原始数组一致）

稀疏数组的优缺点与应用场景

优点

节省存储空间：对于稀疏数据，压缩率极高（如 11×11 的棋盘从 121 个元素压缩到 3 个元素）。
便于数据传输与存储：稀疏数组体积小，适合写入文件或网络传输。
简化处理逻辑：仅关注有效元素，减少无效计算。

缺点

不适合密集数据：若有效元素占比高（如超过 30%），稀疏数组的存储优势会消失，甚至因额外存储位置信息而更占空间。
还原需额外操作：从稀疏数组恢复原始数组需要遍历和填充，增加少量时间开销。

典型应用场景

棋盘类游戏：如五子棋、围棋的棋局保存（大量空位为 0）。
图像处理：黑白图像中大量空白像素（0 值）的压缩存储。
科学计算：稀疏矩阵（如有限元分析中的矩阵）的高效运算。
日志与数据记录：仅记录异常值（非默认状态）的场景。

总结

稀疏数组是处理稀疏数据的高效工具，其核心是通过 “记录元信息 + 有效元素位置” 实现压缩。在有效元素占比极低的场景中，它能显著减少存储空间和传输成本，是数据优化的重要手段。实际应用中，需根据数据的稀疏程度判断是否适用，避免在密集数据上使用反而降低效率