[LC 311] Sparse matrix multiplication

All solutions are pretty intuitive:
1, directly compute each cell in the result matrix, three iterations, when meet zeros, skip.
2, store the location and value for the non-zero cells. There are two ways:
    — Map<Integer, Map<Integer, Integer>> stores (j, (i, A(i,j))) and (j, (k, B(j,k)))
    — List<Integer> store (i, j, A(i, j))
Note that we don’t need to store both A and B into a map/list. Only store A, and then go through the matrix B to find no-zero, calculate the product, and put into the result matrix in one pass.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s