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;
}
}
