LintCode 654 · Sparse Matrix Multiplication (稀疏矩阵乘法)

本文主要是介绍LintCode 654 · Sparse Matrix Multiplication (稀疏矩阵乘法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

654 · Sparse Matrix Multiplication
Algorithms

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]]

解法1：常规解法。没用到稀疏矩阵的优势。

class Solution {
public:/*** @param a: a sparse matrix* @param b: a sparse matrix* @return: the result of A * B*/vector<vector<int>> multiply(vector<vector<int>> &a, vector<vector<int>> &b) {int m = a.size();int n = b.size();if (m == 0 || n == 0) return vector<vector<int>>();int p = b[0].size();vector<vector<int>> res(m, vector<int>(p, 0));for (int i = 0; i < m; i++) {for (int k = 0; k < p; k++) {int sum = 0;for (int j = 0; j < n; j++) {sum += a[i][j] * b[j][k]; }res[i][k] = sum;}}return res;}
};

解法2: 利用了稀疏矩阵的部分优势，也就是当a[i][j] == 0时，省掉k循环。

class Solution {
public:/*** @param a: a sparse matrix* @param b: a sparse matrix* @return: the result of A * B*/vector<vector<int>> multiply(vector<vector<int>> &a, vector<vector<int>> &b) {int m = a.size();int n = b.size();if (m == 0 || n == 0) return vector<vector<int>>();int p = b[0].size();vector<vector<int>> res(m, vector<int>(p, 0));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (a[i][j] == 0) continue;for (int k = 0; k < p; k++) {res[i][k] += a[i][j] * b[j][k]; }}}return res;}
};