311. Sparse Matrix Multiplication

For sparse matrix multiplication, we only need to operate on non zero numbers so that we can save a lot of time on unnecessary multiplications. Other than this, do the multiplication straightforward. Here is a better way to represent the sparse matrix and do the multiplication on it. I'll investigate later: http://www.cs.cmu.edu/~scandal/cacm/node9.html.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {  
4:      int rowA = A.size(), colB = B[0].size(), colA = A[0].size();  
5:      vector<vector<int>> res(rowA, vector<int>(colB, 0));  
6:      for (int i = 0; i < rowA; i++) {  
7:        for (int k = 0; k < colA; k++) {  
8:          if (A[i][k] != 0) {  
9:            for (int j = 0; j < colB; j++) {  
10:              if (B[k][j] != 0) res[i][j] += A[i][k]*B[k][j];  
11:            }  
12:          }  
13:        }  
14:      }  
15:      return res;  
16:    }  
17:  };