# 311 Sparse Matrix Multiplication

Sparse Matrix的矩陣乘法。

• idea: 一開始就想直接按照矩陣乘法的規則刻出來，也就是讓A矩陣中每一row的element和B矩陣中每一col中的element element-wise相乘加總。後來發現會有最後一個case TLE，就處理一下sparse的問題，用矩陣另外將全0的row和col標記成true，就過了。

• 思路（一點點）

        example
        A = 2*3
        B = 3*3
        AB = 2*3
  
        optimize:
        A : col all 0
        B : row all 0
        No need for calculation
  

• code

  public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
  
        int row_a = A.length;
        int col_a = A[0].length;
        int row_b = B.length;
        int col_b = B[0].length;
  
        int[][] AB = new int[row_a][col_b];
        boolean[] A_zero = new boolean[row_a];
        boolean[] B_zero = new boolean[col_b];
  
        //if the col contains all zeros, set to true
        for(int i=0; i<col_b; i++){
            int sum = 0;
            for(int j=0; j<row_b; j++){
                sum+= B[j][i];
            }
            if(sum == 0)
                B_zero[i] = true;
        }
  
        //if the row contains all zeros, set to true
        for(int i=0; i<row_a; i++){
            int sum = 0;
            for(int j=0; j<col_a; j++){
                sum+= A[i][j];
            }
            if(sum == 0)
                A_zero[i] = true;
        }
  
        for(int i=0; i<row_a; i++){
            if(A_zero[i] == true)   continue;
  
            for(int j=0; j<col_b; j++){
                if(B_zero[j] == true)   continue;
  
                int sum = 0;
                for(int k=0; k<col_a; k++){
                    sum += A[i][k]*B[k][j];
                }
                AB[i][j]=sum;
            }
        }
        return AB;
    }
  }