稀疏矩阵乘法全解析：朴素迭代、列表压缩与 Yale（CSR/CSC）格式的 LeetCode 实战指南

稀疏矩阵乘法全解析朴素迭代、列表压缩与 YaleCSR/CSC格式的 LeetCode 实战指南【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以本仓库题解文章 articles/sparse-matrix-multiplication.md 为核心骨架系统讲解稀疏矩阵乘法Sparse Matrix Multiplication的三种递进式解法朴素迭代、列表压缩List of Lists与 Yale 格式CSR/CSC 压缩存储并给出完整的 Python/C 可运行实现与复杂度分析。读完本文你将掌握如何利用矩阵稀疏性跳过零元素计算、用(value, col)对压缩非零项以及用 CSR/CSC 三数组 双指针合并高效完成乘法从而在 LeetCode 及真实工程推荐系统、图计算、科学计算中写出高性能的稀疏矩阵乘法代码。前置知识在深入解法之前建议先确认自己熟悉以下四个概念它们是理解本文三种方案的基石矩阵乘法Matrix Multiplication理解如何用行与列的点积计算结果的每个元素即result[i][j] Σ_k mat1[i][k] * mat2[k][j]。稀疏矩阵概念Sparse Matrix Concepts认识到稀疏矩阵中绝大多数元素为零只有少数非零元素真正参与运算。双指针技术Two-Pointer Technique高效地合并或比较两个有序序列用于第三方案中对两个索引序列做归并。压缩稀疏格式Compressed Sparse Formats理解 CSRCompressed Sparse Row按行压缩与 CSCCompressed Sparse Column按列压缩两种表示法它们是 Yale 方案的基础。问题背景与整体思路给定两个稀疏矩阵mat1尺寸m × k与mat2尺寸k × n要求计算二者的乘积结果矩阵尺寸为m × n。朴素矩阵乘法的三重循环会对每个元素都执行乘加操作即使相乘的一方为零也照算不误——而对于稀疏矩阵这些运算全部是浪费。因此三种方案的共同内核是尽量只让非零元素参与计算区别在于跳过零的粒度与存储结构不同方案存储方式时间复杂度最坏空间复杂度核心技巧1. 朴素迭代原矩阵$O(m \cdot k \cdot n)$$O(1)$遇到mat1的零元素直接跳过2. 列表压缩每行存(value, col)对$O(m \cdot k \cdot n)$$O(m \cdot k k \cdot n)$只遍历非零项3. Yale 格式CSR CSC 三数组$O(m \cdot n \cdot k)$$O(m \cdot k k \cdot n)$双指针归并两个有序索引序列其中 $m$、$k$ 分别是mat1的行数与列数$k$、$n$ 分别是mat2的行数与列数两个矩阵的共享维度必须都是 $k$矩阵乘法才合法。上表的时间复杂度是理论最坏上界矩阵退化为稠密时在矩阵高度稀疏时实际工作量与非零元素个数成正比这也是优化稀疏矩阵乘法的意义所在。方案一朴素迭代Naive Iteration直觉标准矩阵乘法通过mat1的一行 ×mat2的一列的点积来计算结果中的每个元素。对于稀疏矩阵可以跳过所有涉及零元素的计算因为零对结果没有任何贡献。通过在处理mat1中某个元素之前先判断其是否非零就能避免大量无意义的乘法。算法步骤创建尺寸为m x n、全部初始化为零的结果矩阵。遍历mat1的每一行。对行内每个元素检查它是否为非零。若非零则用它乘以mat2对应行即mat2[element_index]中的每个元素并累加到结果矩阵的相应位置。返回结果矩阵。实现Pythonclass Solution: def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) - List[List[int]]: # Product matrix. ans [[0] * len(mat2[0]) for _ in range(len(mat1))] for row_index, row_elements in enumerate(mat1): for element_index, row_element in enumerate(row_elements): # If current element of mat1 is non-zero then iterate over all columns of mat2. if row_element: for col_index, col_element in enumerate(mat2[element_index]): ans[row_index][col_index] row_element * col_element return ans注意这里的循环顺序外层遍历mat1的行与列内层才展开mat2的行且只有mat1元素非零时才进入内层循环。从源码结构看本仓库文章中还提供了等价的 Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 实现以标签页形式组织逻辑与 Python 版完全一致。复杂度分析时间复杂度$O(m \cdot k \cdot n)$空间复杂度$O(1)$仅结果矩阵不计入额外辅助空间其中 $m$ 和 $k$ 分别是mat1的行数和列数$k$ 和 $n$ 分别是mat2的行数和列数。方案二列表压缩List of Lists直觉方案一只是对mat1跳零mat2中的零元素仍会被逐个相乘。为了进一步优化可以预处理两个矩阵只保留非零元素对每一行维护一个(value, column)对列表。这种压缩表示使乘法循环只遍历非零元素对高度稀疏的矩阵非常高效。算法步骤压缩两个矩阵只存非零元素每行生成一个(value, 列索引)对列表。创建尺寸为m x n、初始化为零的结果矩阵。对mat1的每一行遍历其非零元素。对mat1中位于列c的非零元素取出压缩后mat2的第c行。将该mat1元素与mat2那一行的每个非零元素相乘并累加进结果。返回结果矩阵。关键之处由于mat1[i][c]只与mat2[c][j]相乘压缩后我们直接通过B[mat1_col]拿到mat2中所有与当前mat1元素共享下标 c的非零项彻底跳过了两侧的零元素。实现Pythonclass Solution: def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) - List[List[int]]: def compress_matrix(matrix: List[List[int]]) - List[List[int]]: rows, cols len(matrix), len(matrix[0]) compressed_matrix [[] for _ in range(rows)] for row in range(rows): for col in range(cols): if matrix[row][col]: compressed_matrix[row].append([matrix[row][col], col]) return compressed_matrix m len(mat1) k len(mat1[0]) n len(mat2[0]) # Store the non-zero values of each matrix. A compress_matrix(mat1) B compress_matrix(mat2) ans [[0] * n for _ in range(m)] for mat1_row in range(m): # Iterate on all current row non-zero elements of mat1. for element1, mat1_col in A[mat1_row]: # Multiply and add all non-zero elements of mat2 # where the row is equal to col of current element of mat1. for element2, mat2_col in B[mat1_col]: ans[mat1_row][mat2_col] element1 * element2 return ans以A[mat1_row]中的(element1, mat1_col)为外层、B[mat1_col]中的(element2, mat2_col)为内层累加目标直接落到ans[mat1_row][mat2_col]逻辑清晰且无一次零乘法。仓库文章中同样收录了该方案的 Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 版本其中 Java/C 用Pair/pairint,int承载(value, col)。复杂度分析时间复杂度$O(m \cdot k \cdot n)$空间复杂度$O(m \cdot k k \cdot n)$用于存储两个压缩矩阵其中 $m$ 和 $k$ 分别是mat1的行数和列数$k$ 和 $n$ 分别是mat2的行数和列数。注意空间上虽然仍是 $m \cdot k k \cdot n$ 量级但当矩阵稀疏时实际只存储非零元素内存占用远小于原始二维数组。方案三Yale 格式CSR/CSC直觉Yale 格式即压缩稀疏行/列 CSR/CSC是业界表示稀疏矩阵的标准方式。它用三个数组完成压缩values非零元素值、col_index/row_index列/行索引、row_index/col_index行/列指针标记每行/每列在values中的起始位置。对mat1按行压缩CSR、对mat2按列压缩CSC后计算点积就转化为用双指针归并两个有序索引序列达到只遍历非零元素的目的。CSR 与 CSC 三数组结构CSRCompressed Sparse Row按行压缩values按行优先顺序存放所有非零元素的值col_index与values一一对应记录每个非零元素所在的列号row_index长度为行数 1row_index[r]表示第r行的第一个非零元素在values中的起始下标row_index[r 1]表示第r行结束即下一行起点。CSCCompressed Sparse Column按列压缩values按列优先顺序存放所有非零元素的值row_index与values一一对应记录每个非零元素所在的行号col_index长度为列数 1col_index[c]表示第c列的第一个非零元素在values中的起始下标。由于压缩时按行或按列顺序扫描每个行段/列段内部的列号或行号天然是升序排列的这正是后续双指针归并能够成立的前提。算法步骤用 CSR 格式压缩mat1存values、列索引col_index与行指针row_index。用 CSC 格式压缩mat2存values、行索引row_index与列指针col_index。对结果矩阵的每个单元(row, col)取出mat1第row行的非零元素区间A.row_index[row]到A.row_index[row 1]以及mat2第col列的非零元素区间B.col_index[col]到B.col_index[col 1]。用双指针归并这两个区间当mat1的列号与mat2的行号相等时说明共享下标 $k$ 匹配将两值相乘并累加进结果。返回结果矩阵。实现PythonSparseMatrix 类 双指针归并class SparseMatrix: def __init__(self, matrix: List[List[int]], col_wise: bool): self.values, self.row_index, self.col_index self.compress_matrix(matrix, col_wise) def compress_matrix(self, matrix: List[List[int]], col_wise: bool): return self.compress_col_wise(matrix) if col_wise else self.compress_row_wise(matrix) # Compressed Sparse Row def compress_row_wise(self, matrix: List[List[int]]): values [] row_index [0] col_index [] for row in range(len(matrix)): for col in range(len(matrix[0])): if matrix[row][col]: values.append(matrix[row][col]) col_index.append(col) row_index.append(len(values)) return values, row_index, col_index # Compressed Sparse Column def compress_col_wise(self, matrix: List[List[int]]): values [] row_index [] col_index [0] for col in range(len(matrix[0])): for row in range(len(matrix)): if matrix[row][col]: values.append(matrix[row][col]) row_index.append(row) col_index.append(len(values)) return values, row_index, col_index class Solution: def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) - List[List[int]]: A SparseMatrix(mat1, False) B SparseMatrix(mat2, True) ans [[0] * len(mat2[0]) for _ in range(len(mat1))] for row in range(len(ans)): for col in range(len(ans[0])): # Row element range indices mat1_row_start A.row_index[row] mat1_row_end A.row_index[row 1] # Column element range indices mat2_col_start B.col_index[col] mat2_col_end B.col_index[col 1] # Iterate over both row and column. while mat1_row_start mat1_row_end and mat2_col_start mat2_col_end: if A.col_index[mat1_row_start] B.row_index[mat2_col_start]: mat1_row_start 1 elif A.col_index[mat1_row_start] B.row_index[mat2_col_start]: mat2_col_start 1 # Row index and col index are same so we can multiply these elements. else: ans[row][col] A.values[mat1_row_start] * B.values[mat2_col_start] mat1_row_start 1 mat2_col_start 1 return ans双指针合并原理对结果单元ans[row][col]而言它等于mat1第row行的非零元素与mat2第col列的非零元素中列号行号相同的那些对的乘积之和。两个区间的下标序列都是升序的因此用双指针若A.col_index[i] B.row_index[j]说明mat1当前元素的列号偏小不可能在mat2的该列中找到匹配右移i若A.col_index[i] B.row_index[j]说明mat2当前元素的行号偏小右移j若相等则共享维度下标匹配累加A.values[i] * B.values[j]然后i、j同时右移。该过程对每个区间至多线性扫描一遍区间总长即该行/该列的非零元素个数因此在稀疏情况下远快于对整行整列做完整点积。仓库文章中还收录了本方案的 Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 实现其中 C 与 Java 均通过构造函数重载分别构建 CSR默认与 CSCcolWisetrue两种SparseMatrixRust 则用SparseMatrixCSR与SparseMatrixCSC两个独立结构体表达思路与 Python 版完全一致。复杂度分析时间复杂度$O(m \cdot n \cdot k)$最坏上界实际运行时间与参与合并的非零元素数量成正比矩阵越稀疏收益越大空间复杂度$O(m \cdot k k \cdot n)$存储两个压缩矩阵的三数组其中 $m$ 和 $k$ 分别是mat1的行数和列数$k$ 和 $n$ 分别是mat2的行数和列数。常见陷阱Common Pitfalls未跳过第一个矩阵中的零元素稀疏矩阵优化的核心在于当mat1中某元素为零时跳过与其相关的所有乘法。只检查mat2的零元素、或完全不检查都会产生大量无用计算丧失稀疏矩阵乘法的性能优势。方案一的关键正是把if row_element检查放在内层循环之前。混淆乘法中的行列索引矩阵乘法中mat1[i][k]与mat2[k][j]相乘并贡献给result[i][j]。共享维度下标k必须严格对齐结果下标i、j也不能互换——一旦混用轻则结果错误重则数组越界。三种方案中这一点都要反复核对。结果矩阵初始化错误结果矩阵必须以零初始化且尺寸必须是m x n其中m是mat1的行数、n是mat2的列数。尺寸算错会引发索引越界忘记清零则会让累加结果携带脏数据导致求和错误。仓库中的多语言实现与验证本仓库是 NeetCode 风格的 LeetCode 多语言题解集README.md 中声明支持 Python、Java、JavaScript、C、Go、Swift、C#、TypeScript、Rust、Kotlin、Ruby、C、Scala、Dart 等语言。稀疏矩阵乘法这一题当前以完整题解文章的形式存放于 articles/sparse-matrix-multiplication.md三种方案的代码在文章中按标签页组织覆盖 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 共 9 种语言可作为跨语言对拍与面试速查的第一手资料。总结朴素迭代三重循环 对mat1跳零实现最简单是理解后续优化的起点。列表压缩把两个矩阵都压成(value, col)对列表彻底消除零乘法空间换时间是工程上最易读的折中。Yale 格式CSR/CSC用values 索引 指针三数组把mat1按行、mat2按列压缩再用双指针归并两个有序索引序列是工业级稀疏矩阵库如 SciPy 的稀疏矩阵模块采用的标准表示法值得作为面试中展示数据结构与算法结合的高阶答案。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考