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;
}
}
這道題是可以優(yōu)化的敏释，實質上是不按照線性代數里面矩陣相乘的公式去計算已卷，而是分步累加即可. 不過這個方法要求對矩陣乘法蠻熟悉哪轿，知道每一步是誰乘誰腐螟，然后盡量多判斷有沒有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;
}
}
