LeetCode 311. 稀疏矩阵的乘法

2024-04-16 HGNULB 约 5 分钟

文章信息 9 个分类 4 个标签

分类

题目描述

✅ 311. 稀疏矩阵的乘法

题意分析

给两个矩阵 mat1（$m \times p$）和 mat2（$p \times n$），返回它们的乘积矩阵（$m \times n$）。题目保证两者的维度是可乘的，即 mat1 的列数等于 mat2 的行数。

定义本身没有任何歧义：结果中第 i 行第 j 列的元素是 mat1 第 i 行与 mat2 第 j 列的内积，即 $\sum_k mat1[i][k] \times mat2[k][j]$。照定义写就是三重循环。所以这道题真正的考点不在「会不会算矩阵乘法」，而在题面里的那个词——稀疏。

「稀疏」意味着矩阵中绝大多数元素是 0。而乘法有一个显然但极其有用的性质：任何一个乘数为 0，这一项对结果就毫无贡献。既然大部分项都是 0 乘出来的，那就应该在触发乘法之前把它们识别出来并跳过，而不是老老实实做满 $m \times p \times n$ 次乘加。

这里还藏着一个关于循环顺序的信号。教科书写法是 i → j → k，也就是「固定结果的一个格子，把内积一次算完」。这种顺序下 mat1[i][k] 在最内层才被读到，即使它是 0，也只能跳过单独一次乘法。而如果把顺序换成 i → k → j，mat1[i][k] 就被提到了中间层，一次判零可以跳过整整一轮 j 循环。同样是跳零，收益差了 n 倍。

边界要盯住：结果矩阵必须初始化为全 0，因为累加式写法依赖初值；矩阵可能只有一行或一列；元素可以是负数，不能用「非零即正」的假设做任何剪枝；mat2 的列数要从 mat2[0].length 取，不能想当然地用 mat1 的维度。

解法：按共享维度累加非零贡献

核心思路

设 mat1 为 $m \times p$，mat2 为 $p \times n$。普通矩阵乘法满足：
\[answer[i][j] = \sum_{k=0}^{p-1} mat1[i][k] \times mat2[k][j]\]
稀疏矩阵中大量乘积为 0。把循环顺序改为 i → k → j 后，一旦 mat1[i][k] == 0，就能跳过它与 mat2 第 k 行的全部 n 次组合；对于非零项，再把它对所有列的贡献累加到答案。

不变量：处理完共享维度 0...k 后，answer[i][j] 等于这些维度产生的部分点积。每个合法乘积项恰好在自己的 k 被加入一次，因此全部处理后就是标准矩阵乘积。

解题步骤

根据 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(mpn)$。若 mat1 只有 z 个非零元素，实际进入最内层循环的次数为 $O(zn)$，另有 $O(mp)$ 的扫描成本。

空间复杂度：返回矩阵占 $O(mn)$；除此之外只使用 $O(1)$ 额外空间。

关键点总结

矩阵乘法的共享维度是 mat1 的列与 mat2 的行。

i → k → j 的顺序让一个零值可以跳过整段无效计算。

答案格子必须累加所有共享维度的贡献，不能覆盖。

当前实现针对普通二维数组做零值剪枝；只有测量表明扫描仍是瓶颈时才需要稀疏存储格式。

易错点总结

维度取反：结果形状应是 mat1.length × mat2[0].length。

把赋值写成覆盖：必须使用 += 汇总不同 k 的乘积。

使用 mat2[column][k]：正确位置是 mat2[k][column]。

零判断后直接跳过整个结果格子：一个共享维度为零，不代表其他 k 没有贡献。

宣称最坏复杂度低于立方级：不预建稀疏索引时，全非零矩阵仍会执行全部三重循环。

相似题目

题目	难度	考察点
2352. 相等行列对	中等	同样是行与列的配对遍历，但比较的是序列是否相同，可用哈希把 $O(n^3)$ 降到 $O(n^2)$
867. 转置矩阵	简单	行列互换的基本操作，是把 `mat2` 预处理成「按列访问友好」形式的前置技能
73. 矩阵置零	中等	同样围绕零元素做文章，但要求用首行首列当标记位实现 $O(1)$ 额外空间
48. 旋转图像	中等	原地变换矩阵，考察下标映射推导而非稀疏剪枝
54. 螺旋矩阵	中等	按特定路径遍历矩阵，重点在四个边界的收缩与终止条件
59. 螺旋矩阵 II	中等	54 的构造版，把遍历顺序反过来用于填数
304. 二维区域和检索 - 矩阵不可变	中等	二维预处理的代表，用前缀和把区域求和从 $O(mn)$ 降到 $O(1)$
598. 区间加法 II	简单	大量矩阵操作可归约成对边界取最小值，说明「别真的把矩阵算一遍」的思路