1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int[][] multiply(int[][] mat1, int[][] mat2) {
Map<Integer, Map<Integer, Integer>> rowNonZeroPos = new HashMap<>();
for (int row = 0; row < mat1.length; row++) {
Map<Integer, Integer> currRowMap = new HashMap<>();
for (int col = 0; col < mat1[0].length; col++) {
if (mat1[row][col] != 0) {
currRowMap.put(col, mat1[row][col]);
}
}
rowNonZeroPos.put(row, currRowMap);
}
int[][] ans = new int[mat1.length][mat2[0].length];
for (int row = 0; row < ans.length; row++) {
Map<Integer, Integer> currRowMap = rowNonZeroPos.get(row);
for (int col = 0; col < ans[0].length; col++) {
int currPosValue = 0;
for (Map.Entry<Integer, Integer> entry : currRowMap.entrySet()) {
if (mat2[entry.getKey()][col] != 0) {
currPosValue += (mat2[entry.getKey()][col] * entry.getValue());
}
}
ans[row][col] = currPosValue;
}
}
return ans;
}
}
|
记录第一个matrix每一行哪些位置不是0. 然后开始进行multiplication. 当计算某个位置的结果的时候, 我们需要看mat1中该row的每一个值和mat2该col的每个值相乘再最后相加得到的值. 由于我们知道每一个row中mat1非0的位置, 因此我们只需要看与这些非0位置相对应的mat2中的位置是否为0, 如果为0就跳过, 不为0则相乘加到答案上.
时间复杂度: O(m1 * n1 + m2 * n2)
空间复杂度: O(m1 * n1)
