publicclassSolution{ publicint[][] multiply(int[][] A, int[][] B) { int row = A.length, column = B[0].length, colA = A[0].length; int[][] res = newint[row][column]; for (int i = 0; i < row; i++){ for (int j = 0; j < colA; j++){ if (A[i][j] != 0){ for (int k = 0; k < column; k++){ if (B[j][k] != 0){ res[i][k] += A[i][j] * B[j][k]; } } } } } return res; } }
However, this solution still checks matrix B multiple times.
One hash table that build index for non-zero values in each row of Matrix B
publicclassSolution{ publicint[][] multiply(int[][] A, int[][] B) { if (A == null || A[0] == null || B == null || B[0] == null) returnnull; int m = A.length, n = A[0].length, l = B[0].length; int[][] C = newint[m][l]; Map<Integer, HashMap<Integer, Integer>> tableB = new HashMap<>(); //
for(int k = 0; k < n; k++) { tableB.put(k, new HashMap<Integer, Integer>()); for(int j = 0; j < l; j++) { if (B[k][j] != 0){ tableB.get(k).put(j, B[k][j]); } } }
for(int i = 0; i < m; i++) { for(int k = 0; k < n; k++) { if (A[i][k] != 0){ for (Integer j: tableB.get(k).keySet()) { C[i][j] += A[i][k] * tableB.get(k).get(j); } } } } return C; } }