优化311. Sparse Matrix Multiplicat

这里的优化在代码上不是很明显，但实际上是对矩阵乘法非常熟悉才能用得这么溜。这个帖子说得非常清楚为什么可以提高performance from 600ms to 60ms. 关键就是C[i][j]没有被一次就算出来，而是通过多次累计计算。并且因为可以先check A[i][k]是不是为零而省略 B[0].length那么多步。
比如: k = B.length = A[0].length = rowB
C[i][j] = A[i][0]* B[0][j] + A[i][1]* B[2][j]+A[i][2]* B[2][j] + A[i][3]* B[3][j] +...A[i][k]* B[k][j]
摊开来看
C[i][0] = A[i][0]* B[0][0] + A[i][1]* B[1][0]+A[i][2]* B[2][0] + A[i][3]* B[3][0] +...A[i][k]* B[k][0]
C[i][1] = A[i][0]* B[0][1] + A[i][1]* B[1][1]+A[i][2]* B[2][1] + A[i][3]* B[3][1] +...A[i][k]* B[k][1]
C[i][2] = A[i][0]* B[0][2] + A[i][1]* B[1][2]+A[i][2]* B[2][2] + A[i][3]* B[3][2] +...A[i][k]* B[k][2]
...
C[i][j] = A[i][0]* B[0][j] + A[i][1]* B[2][j]+A[i][2]* B[2][j] + A[i][3]* B[3][j] +...A[i][k]* B[k][j]

可以看到A[i][k]要用到j次， which is col次，所以当我们发现A[i][k] == 0时，就可以直接skip掉那个循环。但这并不代表我们就不skip计算C[i][j]了。因为矩阵乘法我们可以分布理解。
看到这个式子，我们的暴力解是一次性找完所有这些factor相乘相加
C[i][j] = A[i][0]* B[0][j] + A[i][1]* B[2][j]+A[i][2]* B[2][j] + A[i][3]* B[3][j] +...A[i][k]* B[k][j]
而优化解法是
C[i][j] += A[i][0]* B[0][j]
+= A[i][1]* B[1][j]
+= A[i][2]* B[2][j]
+= A[i][3]* B[3][j]
+...
+= A[i][k]* B[k][j]

所以相当于太阳绕着A来转，我们在遍历A的每一个点A[i][k]的时候，就在考虑这个A[i][k]用不用得上，用不上（也就是为0）的时候直接就跳过了，因为上面那些式子都会等于0；用得上我们就先加着。

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int row = A.length;
        int col = B[0].length;
        int rowB = A[0].length;
        int[][] C = new int[row][col];
        for (int i = 0; i < row; i++){
            for (int k = 0; k < rowB; k++){
               if(A[i][k] != 0){
                    for (int j = 0; j < col; j++){
                        if (B[k][j] != 0){
                            C[i][j] += A[i][k]*B[k][j];    
                        }
                    }        
                }
            }
        }
        return C;        
    }
}