LeetCode 311. 稀疏矩阵的乘法
题目描述
题意分析
设
mat1的大小为m×p，mat2的大小为p×n，乘积矩阵大小就是m×n。结果的第i行、第j列，等于mat1的第i行与mat2的第j列逐项相乘再求和：$answer[i][j]=\sum_{k=0}^{p-1}mat1[i][k]\times mat2[k][j]$。“稀疏”表示矩阵中有较多的零。零产生的乘积不会改变答案，可以跳过这些贡献，但结果仍需保留完整的矩阵形状。
解法：按共享维度累加非零贡献
核心思路
[!blue]
按
i → k → j的顺序遍历：先固定mat1[i][k]，再把它乘上mat2的第k行，分别累加到结果第i行的各列。这样同一个mat1[i][k]可以统一决定是否需要进入整段列循环。若
mat1[i][k]为零，那么它对所有answer[i][j]的贡献都为零，直接跳过这个k。否则扫描mat2[k]，遇到非零元素才执行乘法与累加。跳过的项全部等于零，保留的项则与矩阵乘法公式逐一对应，因此不会改变结果。处理固定行
i时，在开始第k轮之前，每个answer[i][j]都已经累加了共享维度[0,k)的全部贡献。本轮将第k项加进去后，这个性质继续成立；处理完p个共享位置，就得到了该行每一列的完整点积。所有行分别完成后，整个乘积矩阵即计算完毕。第一矩阵的零值会省掉整段列扫描，而第二矩阵的零判断只省掉乘法和累加，列本身仍然会被访问。因此该实现能利用部分稀疏性，但全非零时仍会进行完整的三重遍历。
解题步骤
- 创建大小为
m×n、初始元素全为零的结果矩阵。- 枚举
mat1的行i和共享维度k。- 若
mat1[i][k]为 0，跳过整个内层列循环。- 否则枚举
mat2的列j；仅当mat2[k][j]非零时累加乘积。- 返回累加完成的结果矩阵。
某行或某列全零时，对应结果自然保持为零。某个共享位置的乘积为零，只能跳过这一项，不能提前结束整个点积；后续位置仍可能产生非零贡献。
代码实现
class Solution {
public int[][] multiply(int[][] mat1, int[][] mat2) {
int rows = mat1.length;
int common = mat1[0].length;
int columns = mat2[0].length;
int[][] answer = new int[rows][columns];
for (int row = 0; row < rows; row++) {
for (int k = 0; k < common; k++) {
// 第一矩阵此项为零，整个共享维度对本行各列都没有贡献。
if (mat1[row][k] == 0) {
continue;
}
for (int column = 0; column < columns; column++) {
if (mat2[k][column] != 0) {
// 不同共享维度的乘积都贡献到同一结果格，必须累加而不是覆盖。
answer[row][column] += mat1[row][k] * mat2[k][column];
}
}
}
}
return answer;
}
}
func multiply(mat1 [][]int, mat2 [][]int) [][]int {
rows := len(mat1)
common := len(mat1[0])
columns := len(mat2[0])
answer := make([][]int, rows)
for row := range answer {
answer[row] = make([]int, columns)
}
for row := 0; row < rows; row++ {
for k := 0; k < common; k++ {
// 第一矩阵此项为零，整个共享维度对本行各列都没有贡献。
if mat1[row][k] == 0 {
continue
}
for column := 0; column < columns; column++ {
if mat2[k][column] != 0 {
// 不同共享维度的乘积都贡献到同一结果格，必须累加而不是覆盖。
answer[row][column] += mat1[row][k] * mat2[k][column]
}
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(mp+mn+zn)$，其中
z是mat1的非零元素数。扫描第一矩阵花费 $O(mp)$，初始化结果花费 $O(mn)$，每个非零项还需扫描第二矩阵的一整行，花费 $O(zn)$；最坏为 $O(mpn)$。- 空间复杂度：额外空间为 $O(1)$；返回的结果矩阵占 $O(mn)$，不计入额外空间。
关键点总结
[!green]
- 共享维度连接
mat1的列和mat2的行，结果下标只保留第一矩阵的行与第二矩阵的列。- 调整遍历顺序不改变累加项，只让第一矩阵的零值能一次跳过整段工作。
- 结果格子保存的是各共享位置贡献的累加和，必须使用
+=。
易错点总结
[!yellow]
- 第二矩阵应访问
mat2[k][column]，不是mat2[column][k]；行列交换会改变含义，也可能越界。- 当前累计值为零不代表后续也为零，只有确定当前乘积为零时才能跳过这一项。
- 第二矩阵的零检查没有跳过列扫描，不能把运行时间只计为非零乘法的次数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 17.26. 稀疏相似度 | 困难 | 同样先按共享索引生成可能非零的组合，避免在大量零结果上做无效计算。 |
| 1570. 两个稀疏向量的点积 | 中等 | 稀疏矩阵每个输出元素是行列点积，可复用只遍历共同非零索引的思想。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！