Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

Input:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

Output:

     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

https://www.jiuzhang.com/qa/337/www.jiuzhang.com

先记录下 B中不为0的坐标

time o(n^3), space o(n*m)

假设矩阵A，B均为 n x n 的矩阵， 矩阵A的稀疏系数为a，矩阵B的稀疏系数为b， a，b∈[0, 1]，矩阵越稀疏，系数越小。

Time O(n^2 * (1 + a * b * n)) = O(n^2 + a * b * n^3) Space O(b * n^2)

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        //
        
        int n = A.length;
        int m = B[0].length;
        int t = A[0].length ;// equals to B.length
            
        int[][] C = new int[n][m];
        
        List<List<Integer>> record = new ArrayList<>(); //record index in B which is not zero
            
        for(int i = 0; i < t ; i++){
            record.add(new ArrayList<>());
            
            for(int j = 0; j < m; j++){
                record.get(i).add(j);
            }
        }
        
        
        for(int i = 0; i < n; i++){
            for(int k = 0; k < t; k++){
                if(A[i][k] == 0)
                    continue;
                
                for(int j : record.get(k)){
                    C[i][j] += A[i][k]*B[k][j];
                }
            }
        }
        
        return C;
    }
}