311. Sparse Matrix Multiplicatio

稀疏矩阵相乘
https://leetcode.com/problems/sparse-matrix-multiplication/
Tag：Hashmap

想法1：
普通矩阵乘法 TLE

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        if(A.size() == 0 || B.size() == 0 || A[0].size() == 0 || B[0].size() == 0) return {{}};
        int m = A.size();
        int n = B[0].size();
        int l = A[0].size();
        if(A[0].size() != B.size())  //error
            return {{}}; 
        vector<vector<int>> C(m, vector<int>(n, 0));
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < l; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        
        return C;
    }
};    

不一样的循环方式，不一样的跳过(28ms)：

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        if(A.size() == 0 || B.size() == 0 || A[0].size() == 0 || B[0].size() == 0) return {{}};
        int m = A.size();
        int n = B[0].size();
        int l = A[0].size();
        if(A[0].size() != B.size())  //error
            return {{}}; 
        vector<vector<int>> C(m, vector<int>(n, 0));
        
        for(int i = 0; i < m; i++) {
            for(int k = 0; k < l; k++) {
                if(A[i][k] == 0) continue;
                for(int j = 0; j < n; j++) {
                    if(B[k][j] == 0) continue;
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        
        return C;
    }
};

想法2：
跳过全0的行、列

想法3：
只计算非全0的行、列

用自己的想法实现了一下，结果比想法1慢。(36ms)

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        if(A.size() == 0 || B.size() == 0 || A[0].size() == 0 || B[0].size() == 0) return {{}};
        int m = A.size();
        int n = B[0].size();
        int l = A[0].size();
        if(A[0].size() != B.size())  //error
            return {{}}; 
        vector<vector<int>> C(m, vector<int>(n, 0));
        
        unordered_map<int,set<int>> mpA; //non-allzero rows
        unordered_map<int,set<int>> mpB; //non-allzero columns
        
        for(int i = 0; i < m; i++)
            for(int j = 0; j < l; j++)
                if(A[i][j] != 0)
                    mpA[i].insert(j);
        for(int i = 0; i < l; i++)
            for(int j = 0; j < n; j++)
                if(B[i][j] != 0)
                    mpB[j].insert(i);
        
        for(auto &a: mpA) {
            for(auto &b: mpB) {
                int i = a.first;
                int j = b.first;
                for(auto &k: a.second) {
                    if(B[k][j] == 0) continue;
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        
        return C;
    }
};