题目地址：

https://www.lintcode.com/problem/sparse-matrix-multiplication/description

给定两个稀疏矩阵$A$和$B$，分别是$m\times n$和$n\times l$，求它们的乘积$AB$。

直接按照矩阵乘法的定义去算即可。枚举$A$的每一项，计算其在$AB$中的贡献（$A[i][j]$对于$AB$的贡献只在于$AB$的下标为$j$的行），当遇到$0$的时候跳过。代码如下：

public class Solution { /** * @param A: a sparse matrix * @param B: a sparse matrix * @return: the result of A * B */ public int[][] multiply(int[][] A, int[][] B) { // write your code here int[][] C = new int[A.length][B[0].length]; for (int i = 0; i < A.length; i++) { for (int j = 0; j < A[0].length; j++) { // 遇到0则跳过 if (A[i][j] != 0) { for (int k = 0; k < B[0].length; k++) { C[i][k] += A[i][j] * B[j][k]; } } } } return C; } }

时间复杂度$O(mnl)$（实际上取决于$A$的稀疏程度），空间$O(1)$。