Medium
Sparse matrix意思是0很多的矩阵，所以这道题为了不TLE要检查0及时跳过，毕竟乘法里边有一个乘数为零就没有意义再乘了. 我用的Brute force矩阵乘法.
class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int row = A.length;
int n = A[0].length;
int col = B[0].length;
int[][] C = new int[row][col];
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
for (int k = 0; k < n; k++){
if (A[i][k] == 0 || B[k][j] == 0){
continue;
} else {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
return C;
}
}
这道题是可以优化的，实质上是不按照线性代数里面矩阵相乘的公式去计算，而是分步累加即可. 不过这个方法要求对矩阵乘法蛮熟悉，知道每一步是谁乘谁，然后尽量多判断有没有0，尽早排除不必要的计算.
image.png
class Solution {
public int[][] multiply(int[][] A, int[][] B) {
int row = A.length;
int n = A[0].length;
int col = B[0].length;
int[][] C = new int[row][col];
for (int i = 0; i < row; i++){
for (int j = 0; j < n; j++){
if (A[i][j] != 0){
for (int k = 0; k < col; k++){
if (B[j][k] != 0){
C[i][k] += A[i][j] * B[j][k];
}
}
}
}
}
return C;
}
}
