深入理解稀疏数组：压缩存储与转换实现（Java 版）

在程序开发中，我们经常需要处理二维数组。然而当数组中绝大部分元素都是默认值（例如 0）时，直接存储完整的二维结构会浪费大量内存和计算资源。稀疏数组 正是为了解决这类“数据稀疏”问题而设计的一种紧凑存储结构。本文将系统介绍稀疏数组的概念、适用场景以及 Java 中二维数组与稀疏数组相互转换的思路与实现。

1. 应用场景：为什么要引入稀疏数组？

来看一个典型的稀疏二维数组 Arr1[8][7]（8 行 7 列），其中大部分位置都是 0，只有少量元素为 1 或 2：


0	0	0	0
1	0	0	0
0	0	0	2
0	2	0	0
0	0	1	0
0	0	0	0
0	0	0	0
0	0	0	0

对于这样的数组，无论存入文件还是在内存中处理，大量的 0 都是无意义的数据，却占据着存储空间，遍历时也需要检查每一个位置，效率低下。稀疏数组可以将这些离散的有效数据集中存储，极大减少空间占用和访问开销。这种场景在棋盘游戏（如五子棋、围棋）、地图栅格数据、矩阵运算等中十分常见。

2. 什么是稀疏数组？

稀疏数组的本质是只记录原数组中非默认值元素的位置和值，并用一个固定格式的结构把它们组织起来。

以上面的 Arr1 为例，它共有 8 行 7 列，其中非零数据有 4 个。转换为稀疏数组后的结果如下表所示：

行索引 (row)	列索引 (col)	值 (value)
8	7	4
1	1	1
2	6	2
3	2	2
4	4	1

稀疏数组的特点可以概括为：

第一行：记录原数组的行数、列数、有效数据个数。
后续每一行：记录一个有效数据的行索引、列索引和具体数值。

这样，一个 8×7 的原数组就被压缩成了一个 5×3 的小数组（有效数据个数 + 1 行，固定 3 列），存储和传输的开销大幅下降。

3. 二维数组与稀疏数组的转换思路

在设计转换逻辑时，可以遵循清晰的步骤：

3.1 二维数组 → 稀疏数组

遍历原二维数组，统计所有非默认值（非零）的元素个数 sum。
根据 sum 创建稀疏数组 sparseArr[sum+1][3]。
将原数组的行数、列数、sum填入稀疏数组的第一行。
再次遍历原数组，每遇到一个非零元素，就将其行号、列号、值依次填入稀疏数组的下一个可用行。

3.2 稀疏数组 → 二维数组

读取稀疏数组的第一行，得到原数组的总行数、总列数，据此创建目标二维数组（通常初始化为全 0）。
从稀疏数组的第二行开始，依次读取每一行，将对应的值赋给二维数组中指定位置。
完成后即可得到恢复后的完整二维数组。

时间复杂度均为 O(m × n)，与二维数组规模相关，但存储和 IO 压力大大减轻。

4. 二维数组到稀疏数组的具体实现（Java）

下面通过完整的 Java 代码来演示上述转换过程。

4.1 准备原始二维数组并输出

// 创建原始二维数组 8*7
int[][] Arr1 = new int[8][7];
// 存入有效数据
Arr1[1][1] = 1;
Arr1[2][6] = 2;
Arr1[3][2] = 2;
Arr1[4][4] = 1;

// 输出原始的二维数组
System.out.println("这是原始的二维数组：");
for (int[] row : Arr1) {
    for (int data : row) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}

4.2 统计有效数据个数

int sum = 0;
for (int i = 0; i < Arr1.length; i++) {
    for (int j = 0; j < Arr1[i].length; j++) {
        if (Arr1[i][j] != 0) {
            sum++;
        }
    }
}
System.out.println("有效数据个数 sum = " + sum);  // 输出 4

4.3 创建稀疏数组并填充首行

// 创建稀疏数组，行数为 sum+1，列数为 3
int[][] sparseArr = new int[sum + 1][3];

// 第一行存储原数组的规模及有效数据个数
sparseArr[0][0] = Arr1.length;        // 原数组行数
sparseArr[0][1] = Arr1[0].length;     // 原数组列数
sparseArr[0][2] = sum;                // 有效数据个数

这里使用 Arr1.length 和 Arr1[0].length 动态获取行列数，让代码具备更好的通用性，即使原数组大小改变也无需修改逻辑。

4.4 将有效数据逐个填入稀疏数组

int count = 0;  // 记录当前已填入的有效数据个数（也作为稀疏数组的行指针）
for (int i = 0; i < Arr1.length; i++) {
    for (int j = 0; j < Arr1[i].length; j++) {
        if (Arr1[i][j] != 0) {
            count++;
            sparseArr[count][0] = i;            // 行索引
            sparseArr[count][1] = j;            // 列索引
            sparseArr[count][2] = Arr1[i][j];   // 值
        }
    }
}

4.5 输出稀疏数组进行验证

System.out.println("转换后的稀疏数组：");
for (int i = 0; i < sparseArr.length; i++) {
    System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
}

此时输出的结果将与第二节中的稀疏数组表格完全一致。

5. 稀疏数组恢复为二维数组

将稀疏数组还原成原始的二维数组同样简单。

5.1 读取首行，创建目标二维数组

1 2	// 根据稀疏数组第一行信息创建新的二维数组 int[][] Arr2 = new int[sparseArr[0][0]][sparseArr[0][1]];

5.2 遍历稀疏数组剩余行，赋值给二维数组

// 从索引 1 开始，遍历所有有效数据行
for (int i = 1; i <= sparseArr[0][2]; i++) {
    Arr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}

5.3 输出恢复后的二维数组

System.out.println("恢复后的二维数组：");
for (int[] row : Arr2) {
    for (int data : row) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}