311. Sparse Matrix Multiplication

Given twosparse matricesAandB, return the result ofAB.

You may assume thatA's column number is equal toB's row number.

Example:

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 |

S1: brutal force O(MNK)

    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int rowA = A.size();
        if (rowA == 0) return vector<vector<int>>{};
        int colA = A[0].size();
        int rowB = B.size();
        if (rowB == 0) return vector<vector<int>>{};
        int colB = B[0].size();
        vector<vector<int>> result(rowA, vector<int>(colB));
        for (int i = 0; i < rowA; ++i) {
            for (int j = 0; j < colB; ++j) {
                for (int k = 0; k < colA; ++k) {
                    if (A[i][k] != 0 && B[k][j] != 0) {
                        result[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
        return result;
    }

S2: 剪枝

若A[i][k] = 0 那么它与B第k行所有元素的乘积都为0，不用计算。也就是只在A有值的时候进行计算

    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int rowA = A.size();
        if (rowA == 0) return vector<vector<int>>{};
        int colA = A[0].size();
        int rowB = B.size();
        if (rowB == 0) return vector<vector<int>>{};
        int colB = B[0].size();
        vector<vector<int>> result(rowA, vector<int>(colB));
        for (int i = 0; i < rowA; ++i) {
            for (int k = 0; k < colA; ++k) {
                if (A[i][k] != 0) {
                    for (int j = 0; j < colB; ++j) {
                        if (B[k][j] != 0) {
                            result[i][j] += A[i][k] * B[k][j];
                        }
                    }
                }
            }
        }
        return result;
    }

S3: hashmap

用hashhap来表示sparse matrix。这一题最主要的是设计合适的data structure来表示matrix

    //has compiler error

    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int m = A.size();
        int n = B.size();
        int k = B[0].size();
        vector<vector<int>> result(m, vector<int>(k, 0));
        unordered_map<int, unordered_map<int, int>> sparseA;
        unordered_map<int, unordered_map<int, int>> sparseB;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (A[i][j] != 0) {
                    sparseA[i][j] = A[i][j];
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < k; ++j) {
                if (B[i][j] != 0) {
                    sparseB[i][j] = B[i][j];
                }
            }
        }
        for (auto a : sparseA) {
            int x = a.first;
            for (auto i : sparseA[x]) {
                int y = i.first;
                int valA = i.second;
                for (auto b : sparseB[y]) {
                    result[x][b.first] += valA * b.second;
                }
            }
        }
        return result;
    }