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
