Sparse Matrix Multiplication

题目地址：
https://leetcode.com/problems/sparse-matrix-multiplication/#/description
https://discuss.leetcode.com/topic/199/dot-product-of-sparse-vector/4

题目：

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 |

解题思路：
这道题就是正常的matrix乘法，需要注意的是可以通过判断元素是否为零来节省时间。这道题会有followup：如果是排好序的话，是可以降低复杂度的：


代码：

public int[][] multiply(int[][] A, int[][] B) {
    int m = A.length;
    int n = A[0].length;
    int nb = B[0].length;
    int[][] rst = new int[m][nb];
    for(int i = 0; i <= m - 1; i++){
        for(int j = 0; j <= nb - 1; j++){
            int curr = 0;
            for(int k = 0; k <= n - 1; k++){
                if(A[i][k] != 0 && B[k][j] != 0){
                    curr += A[i][k] * B[k][j];
                }
            }
            rst[i][j] = curr;
        }
    }
    return rst;
}