654. Sparse Matrix Multiplicatio

Description

Given two Sparse Matrix A and B, return the result of AB.

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

Example

Example1

Input:

[[1,0,0],[-1,0,3]]

[[7,0,0],[0,0,0],[0,0,1]]

Output:

[[7,0,0],[-7,0,3]]

Explanation:

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 |

Example2

Input:

[[1,0],[0,1]]

[[0,1],[1,0]]

Output:

[[0,1],[1,0]]

思路：

第一种直接按照矩阵乘法的规则计算，时间复杂度是三层循环乘起来，第二种呢从A矩阵出发，跳过为0的元素按列循环，时间复杂度会少一部分为0的元素的。

代码：