题目重点：从零设计稀疏矩阵结构，只遍历能产生乘积的非零项，解释重复坐标、抵消为零和真正的复杂度。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练代码使用 COO 三元组构造 rows×cols 矩阵，重复坐标数值相加，最终为 0 的项不存；乘法仅适用于 A.cols=B.rows。
- 题目未说明整数/浮点、是否有转置、返回数据结构或零值近似判断；训练版用整数示例。
解题路线
- 按行存字典 row→{col:value}，只保留非零。对 A 每个非零 A[i,k]，遍历 B 第 k 行所有非零 B[k,j]，把乘积累加到输出 (i,j)。这等价于对连接键 k 做稀疏 join。
- 构造时合并重复坐标；乘法后若不同路径的贡献抵消为 0，要删除该项，否则存储不再保持真正稀疏。
- 内存上输出占实际非零结果，而临时行累加器占该输出行可能命中的列数；若一行输出特别稠密，它可以接近 B.cols，无法保证每行都小。
- 若 B 是列压缩 CSC，可按交集求单个 dot，但计算全矩阵输出时按 B 的行遍历更自然；具体选 CSR/COO/CSC 应看构建频率、乘法方向和读写模式。
手动走一遍
A 的第 0 行有 A[0,1]=2，B 第 1 行有 B[1,3]=4，则结果 C[0,3] 加 8；若另一 k 路径贡献 −8，C[0,3] 被删除。A.cols 与 B.rows 不等时直接报维度错误。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class SparseMatrix:
"""Rows store only nonzero columns. Duplicate input coordinates sum."""
def __init__(self, rows: int, cols: int, entries=()):
if rows < 0 or cols < 0:
raise ValueError("negative dimension")
self.rows, self.cols = rows, cols
self.data = {}
for i, j, value in entries:
if not (0 <= i < rows and 0 <= j < cols):
raise IndexError("coordinate out of range")
if value:
row = self.data.setdefault(i, {})
new = row.get(j, 0) + value
if new:
row[j] = new
else:
del row[j]
if not row:
del self.data[i]
def multiply(self, other: "SparseMatrix") -> "SparseMatrix":
if self.cols != other.rows:
raise ValueError("dimension mismatch")
result = SparseMatrix(self.rows, other.cols)
for i, row in self.data.items():
output = {}
for k, left_value in row.items():
for j, right_value in other.data.get(k, {}).items():
output[j] = output.get(j, 0) + left_value * right_value
output = {j: value for j, value in output.items() if value}
if output:
result.data[i] = output
return result
复杂度
设 A 第 i 行非零列集合 Kᵢ，B 第 k 行非零数 nnz(Bₖ)，乘法工作量为 ΣᵢΣ_{k∈Kᵢ}nnz(Bₖ)，外加构造/输出遍历；空间 O(nnz(A)+nnz(B)+nnz(C)) 加临时输出行。不能粗略声称总是 O(nnz(A)+nnz(B))。训练代码经 10,000 组随机矩阵与独立稠密乘法 oracle 对照。
易错点与追问
容易失分的边界
- 先分配 rows×cols 输出，即使只有少量非零项。
- 把复杂度写成 O(MN) 或 O(nnz(A)+nnz(B)) 而不计交叉乘积。
- 重复坐标覆盖而非相加。
- 抵消为 0 后仍保存该坐标。
- 矩阵维度不匹配时返回无意义结果。
继续深挖
- 若 B 常复用，怎样缓存按行索引？
- 稀疏向量点积如何用双指针或 hash？
- 乘积突然变稠密时如何切换表示？
- 浮点近零应按什么阈值剔除？
