稀疏数组 作者:马育民 • 2026-01-31 22:01 • 阅读:10002 # 介绍 **稀疏数组(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