Fork me on GitHub

Sparse Matrix Multiplication

Posted on

Description

https://leetcode.com/problems/sparse-matrix-multiplication/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int a = A.size();
        int b = B.size();
        int c = B[0].size();
        unordered_map<int, unordered_map<int, int>> rowAMap;
        unordered_map<int, unordered_map<int, int>> columnBMap;
        for (int i = 0; i < a; ++i) {
            for (int j = 0; j < b; ++j) {
                if (A[i][j]) {
                   rowAMap[i][j] = A[i][j]; 
                }
            }
        }
        
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < b; ++j) {
                if (B[j][i]){
                    columnBMap[i][j] = B[j][i];
                }
            }
        }
        
        vector<vector<int>> ret(a, vector<int>(c, 0));
        for (auto& item1 : rowAMap) {
            int row = item1.first;
            for (auto& item2 : columnBMap) {
                int column = item2.first;
                int sum = 0;
                for (auto& item3 : item1.second){
                    sum += item2.second[item3.first] * item3.second;
                }
                ret[row][column] = sum;
            }
            
        }
        return ret;
        
    }
};