Leetcode - Sparse Matrix Multiplication

My code:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        if (A == null || B == null || A.length == 0 || A[0].length == 0 || B.length == 0 || B[0].length == 0) {
            return null;
        }
        
        int m = A.length;
        int n = A[0].length;
        int l = B[0].length;
        HashMap<Integer, Map<Integer, Integer>> tableB = new HashMap<Integer, Map<Integer, Integer>>();
        int[][] ret = new int[m][l];
        
        for (int i = 0; i < n; i++) {
            tableB.put(i, new HashMap<Integer, Integer>());
            for (int j = 0; j < l; j++) {
                if (B[i][j] != 0) {
                    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) {
                    Map<Integer, Integer> map = tableB.get(j);
                    for (Integer k : map.keySet()) {
                        ret[i][k] += A[i][j] * map.get(k);
                    }
                }
            }
        }
        
        return ret;
    }
}

reference:
https://discuss.leetcode.com/topic/30626/java-and-python-solutions-with-and-without-tables

看了答案写出来的。
本来的时间复杂度是， O(m * n * n * l)
现在的时间复杂度是， O(m * n + n * l) 考虑到稀疏矩阵

用一个 HashMap 保存下， B 中，每一行非0得元素，已经他们的列号。

遍历 A, 每到 (i, j)
就去 B中， 找出， 第 j 行，所有的非零元素 (HashMap 即可做到。)，比如， B[j][k]
然后累加到 c[i][k] 上。

差不多就这样了。

Anyway, Good luck, Richardo! -- 09/22/2016