题目描述
给出两个稀疏矩阵A和B, 返回他们的乘积。
A的列数一定等于B的行数。
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.
Constraints:
1 <= A.length, B.length <= 100
1 <= A[i].length, B[i].length <= 100
-100 <= A[i][j], B[i][j] <= 100
样例
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 |
算法1
(数据压缩)
由于是稀疏数组可以只计算非零数字。
将A矩阵转存为hashmap,然后对每一个非零数遍历B的列数来更新它在ans矩阵里可以被用到的位置。
时间复杂度
遍历A、B矩阵
C++ 代码
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
int n = A.size(), m = A[0].size(), k = B[0].size();
vector<vector<int>> res(n, vector<int>(k, 0));
unordered_map<int, int> am;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
{
if (!A[i][j]) continue;
int idx = i * m + j;
am[idx] = A[i][j];
}
for (auto aij : am)
{
int va = aij.second, aidx = aij.first, ai = aidx / m, aj = aidx % m;
for (int j = 0; j < k; j ++)
{
res[ai][j] += va * B[aj][j];
}
}
return res;
}
};