今天和大家聊的问题叫做 稀疏矩阵的乘法，我们先来看题面：https://leetcode-cn.com/problems/sparse-matrix-multiplication/
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.
给你两个 稀疏矩阵 A 和 B，请你返回 AB 的结果。你可以默认 A 的列数等于 B 的行数。
示例
解题
由于是稀疏数组可以只计算非零数字。将A矩阵转存为hashmap,然后对每一个非零数遍历B的列数来更新它在ans矩阵里可以被用到的位置。
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; } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
