leetcode-311. 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.
原题地址

虽然归在hash table类别下，似乎不用hash table会更快一些。代码如下：

vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
    int row = A.size(), col = B[0].size(), n = B.size();
    vector<vector<int>> C(row, vector<int>(col, 0));
    for (int i = 0; i < row; i++) {
        for (int k = 0; k < n; k++) {
            if (A[i][k] != 0)
                for (int j = 0; j < col; j++)
                    if (B[k][j] != 0)
                        C[i][j] += A[i][k] * B[k][j];
        }
    }
    return C;
}