leetcode：311. 稀疏矩阵的乘法（会员题）
lintcode：654 · 稀疏矩阵乘法

题目

给定两个 稀疏矩阵 A 和 B，返回 AB 的结果。
您可以假设 A 的列数等于 B 的行数。

示例：

输入：
[[1,0,0],[-1,0,3]]
[[7,0,0],[0,0,0],[0,0,1]]
输出：
[[7,0,0],[-7,0,3]]
解释：
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 |

输入：
[[1,0],[0,1]]
[[0,1],[1,0]]
输出：
[[0,1],[1,0]]

解答 & 代码

解法一：模拟（暴力，三重循环）

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 rows = a.size();        // 结果矩阵的行数（a 矩阵的行数）
        int cols = b[0].size();        // 结果矩阵的列数（b 矩阵的列数）
        int dim = a[0].size();        // 中间维度（a 矩阵的列数、b 矩阵的行数）
        vector<vector<int>> result(rows, vector<int>(cols, 0));    // 结果矩阵
        // 三重循环
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                // 计算 result[i][j]，等于 a 矩阵第 i 行和 b 矩阵第 j 列对应元素相乘再求和
                for(int k = 0; k < dim; ++k)
                    result[i][j] += a[i][k] * b[k][j];
            }
        }
        return result;
    }
};

复杂度分析：设 a 矩阵 rows 行 dim 列，b 矩阵 dim 行 cols 列

• 时间复杂度 O(rows cols dim)：
• 空间复杂度 O(1)：结果矩阵的空间复杂度不计入

执行结果：

执行结果：通过
执行用时：61 ms, 在所有 C++ 提交中击败了 57.80% 的用户
内存消耗：5.41 MB, 在所有 C++ 提交中击败了 57.80% 的用户

解法二：哈希表存储稀疏矩阵

class Solution {
private:
    // 用哈希表存储稀疏矩阵matrix的非零元素，key = 行号，val = 哈希表(key=列号，val=非零元素值)
    unordered_map<int, unordered_map<int, int>> saveSparseMatrix(vector<vector<int>> &matrix, int rows, int cols)
    {
        unordered_map<int, unordered_map<int, int>> hashMap;
        for(int i = 0; i < rows; ++i)
        {
            unordered_map<int, int> rowMap;
            for(int j = 0; j < cols; ++j)
            {
                if(matrix[i][j] != 0)        // 哈希表中只存储非零元素
                    rowMap[j] = matrix[i][j];
            }
            hashMap[i] = rowMap;
        }
        return hashMap;
    }
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();        // 结果矩阵的行数（a 矩阵的行数）
        int K = a[0].size();    // 结果矩阵的列数（b 矩阵的列数）
        int N = b[0].size();    // 中间维度（a 矩阵的列数、b 矩阵的行数）
        vector<vector<int>> result(M, vector<int>(N, 0));    // 结果矩阵
        // 分别用哈希表存储矩阵 a、矩阵 b 的非零元素
        unordered_map<int, unordered_map<int, int>> aMap = saveSparseMatrix(a, M, K);
        unordered_map<int, unordered_map<int, int>> bMap = saveSparseMatrix(b, K, N);
        for(int i = 0; i < M; ++i)
        {
            unordered_map<int, int> aiMap = aMap[i];
            // 遍历矩阵 a 的每个非零元素 aik（第 i 行第 k 列个元素）
            for(auto itA = aiMap.begin(); itA != aiMap.end(); ++itA)
            {
                int k = itA->first;
                int aik = itA->second;
                unordered_map<int, int> bkMap = bMap[k];
                // 遍历矩阵 b 的第 k 行非零元素 bkj
                // 因为矩阵 a 的第 k 列元素会和矩阵 b 第 k 行的每个元素相乘，加到 result[i][j]
                for(auto itB = bkMap.begin(); itB != bkMap.end(); ++itB)
                {
                    int j = itB->first;
                    int bkj = itB->second;
                    result[i][j] += aik * bkj;
                } 
            }
        }
        return result;
    }
};

执行结果：

执行结果：通过
执行用时：41 ms, 在所有 C++ 提交中击败了 98.40% 的用户
内存消耗：4.58 MB, 在所有 C++ 提交中击败了 98.40% 的用户