311. Sparse Matrix Multiplication

Description

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.

Example:

example

Solution

HashMap, time O(m * max(n, l)), space O(n * l)

因为给定的matrix是稀疏矩阵，所以我们要做一些对于0的预处理。
由于C[i][k] = A[i][x] * B[x][k], 0 <= x <= n
我们可以用一个HashMap，将B中每行不为0的元素保存下来。
然后遍历A，将每个不为0的元素累加到C中去。

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        if (A == null || A[0] == null || B == null || B[0] == null) {
            return null;
        }
        
        int m = A.length;
        int n = A[0].length;
        int l = B[0].length;
        int[][] C = new int[m][l];
        
        Map<Integer, Map<Integer, Integer>> tableB = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            tableB.put(i, new HashMap<>());
            
            for (int j = 0; j < l; ++j) {
                if (B[i][j] == 0) {
                    continue;
                }
                tableB.get(i).put(j, B[i][j]);
            }
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (A[i][j] == 0) {
                    continue;
                }
                
                for (Map.Entry<Integer, Integer> entry : tableB.get(j).entrySet()) {
                    C[i][entry.getKey()] += A[i][j] * entry.getValue();
                }
            }
        }
        
        return C;
    }
}