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

稀疏矩阵乘法全解析：朴素迭代、列表压缩与 Yale（CSR/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）：理解 CSR（Compressed Sparse Row，按行压缩）与 CSC（Compressed 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中某个元素之前先判断其是否非零，就能避免大量无意义的乘法。

算法步骤

1. 创建尺寸为m x n、全部初始化为零的结果矩阵。
2. 遍历mat1的每一行。
3. 对行内每个元素，检查它是否为非零。
4. 若非零，则用它乘以mat2对应行（即mat2[element_index]）中的每个元素，并累加到结果矩阵的相应位置。
5. 返回结果矩阵。

实现（Python）

class 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)对列表。这种压缩表示使乘法循环只遍历非零元素，对高度稀疏的矩阵非常高效。

算法步骤

1. 压缩两个矩阵，只存非零元素：每行生成一个(value, 列索引)对列表。
2. 创建尺寸为m x n、初始化为零的结果矩阵。
3. 对mat1的每一行，遍历其非零元素。
4. 对mat1中位于列c的非零元素，取出压缩后mat2的第c行。
5. 将该mat1元素与mat2那一行的每个非零元素相乘并累加进结果。
6. 返回结果矩阵。

关键之处：由于mat1[i][c]只与mat2[c][j]相乘，压缩后我们直接通过B[mat1_col]拿到mat2中所有与当前mat1元素"共享下标 c"的非零项，彻底跳过了两侧的零元素。

实现（Python）

class 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/pair<int,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 三数组结构

CSR（Compressed Sparse Row，按行压缩）：

• values：按行优先顺序存放所有非零元素的值；
• col_index：与values一一对应，记录每个非零元素所在的列号；
• row_index：长度为行数 + 1，row_index[r]表示第r行的第一个非零元素在values中的起始下标，row_index[r + 1]表示第r行结束（即下一行起点）。

CSC（Compressed Sparse Column，按列压缩）：

• values：按列优先顺序存放所有非零元素的值；
• row_index：与values一一对应，记录每个非零元素所在的行号；
• col_index：长度为列数 + 1，col_index[c]表示第c列的第一个非零元素在values中的起始下标。

由于压缩时按行（或按列）顺序扫描，每个行段/列段内部的列号（或行号）天然是升序排列的，这正是后续双指针归并能够成立的前提。

算法步骤

1. 用 CSR 格式压缩mat1：存values、列索引col_index与行指针row_index。
2. 用 CSC 格式压缩mat2：存values、行索引row_index与列指针col_index。
3. 对结果矩阵的每个单元(row, col)，取出mat1第row行的非零元素区间（A.row_index[row]到A.row_index[row + 1]）以及mat2第col列的非零元素区间（B.col_index[col]到B.col_index[col + 1]）。
4. 用双指针归并这两个区间：当mat1的列号与mat2的行号相等时，说明共享下标 $k$ 匹配，将两值相乘并累加进结果。
5. 返回结果矩阵。

实现（Python：SparseMatrix 类 + 双指针归并）

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（默认）与 CSC（colWise=true）两种SparseMatrix，Rust 则用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