LeetCode 311. Sparse Matrix Multiplication

原题链接在这里：https://leetcode.com/problems/sparse-matrix-multiplication/description/

题目：

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:

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

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


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

题解：

按照两个矩阵相乘的公式计算结果.

Since It is spase, skip k loop when A[i][j] == 0.

Time Complexity: O(m*n*o). m = A.length, n = A[0].length, o = B[0].length.

Space: O(1). regardless res.

AC Java:

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int m = A.length;
        int n = A[0].length;
        int o = B[0].length;
        
        int [][] res = new int[m][o];
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if(A[i][j] != 0){
                    for(int k = 0; k<o; k++){
                        res[i][k] += A[i][j]*B[j][k];
                    }
                }
            }
        }
        return res;
    }
}