稀疏数组（Sparse Array）：高效压缩稀疏数据的优化方案
稀疏数组是一种针对大部分元素为默认值（如 0、null） 的二维数组设计的压缩存储结构，通过仅记录有效元素的位置和值，大幅减少存储空间和数据传输开销。本文详细解析稀疏数组的原理、转换流程、应用场景及实现代码。
稀疏数组的核心概念
适用场景
当一个二维数组中：
- 绝大多数元素是默认值（如 0、空值）；
- 仅有少量元素具有实际意义（如 1、2 等非默认值）。
此时直接存储原始数组会造成大量空间浪费，而稀疏数组通过 “保留有效信息，舍弃默认值” 实现压缩。
核心思想
稀疏数组不存储默认值，仅记录：
- 原始数组的总行数、总列数；
- 所有非默认值元素的位置（行号、列号）和值。
原始数组与稀疏数组的转换
以五子棋棋盘为例（11×11 的二维数组，0 表示空位，1 表示黑子，2 表示白子），演示转换过程。
原始数组（11×11）
1
2
3
| int[][] chessBoard = new int[11][11];
chessBoard[1][2] = 1;
chessBoard[2][3] = 2;
|
原始数组中，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：填充稀疏数组
将原始数组中的有效元素依次填入稀疏数组：
1
2
3
4
| 稀疏数组（3行3列）：
[11, 11, 2] → 元信息：11行、11列、2个有效元素
[1, 2, 1] → 第1行第2列的值为1（黑子）
[2, 3, 2] → 第2行第3列的值为2（白子）
|
从稀疏数组还原原始数组
步骤 1：创建空的原始数组
根据稀疏数组第 0 行的元信息，初始化一个rows × cols的二维数组：
1
2
3
| int rows = sparse[0][0];
int cols = sparse[0][1];
int[][] restored = new int[rows][cols];
|
步骤 2：填充有效元素
遍历稀疏数组第 1 至 count 行，将每个元素的行号、列号和值还原到原始数组：
1
2
3
4
5
6
| 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）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| public class SparseArrayDemo {
public static void main(String[] args) {
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();
}
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++;
}
}
}
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;
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]);
}
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();
}
}
}
|
输出结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 原始数组：
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 值）的压缩存储。
- 科学计算：稀疏矩阵（如有限元分析中的矩阵）的高效运算。
- 日志与数据记录：仅记录异常值（非默认状态）的场景。
总结
稀疏数组是处理稀疏数据的高效工具，其核心是通过 “记录元信息 + 有效元素位置” 实现压缩。在有效元素占比极低的场景中，它能显著减少存储空间和传输成本，是数据优化的重要手段。实际应用中，需根据数据的稀疏程度判断是否适用，避免在密集数据上使用反而降低效率