?LeetCode刷題實戰(zhàn)311：稀疏矩陣的乘法
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.
示例
解題
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;
}
};