BiruLyu
8/14/2017 - 9:19 PM

## 311. Sparse Matrix Multiplication(Approach#1).java

``````public 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, n = A[0].length, l = B[0].length;
int[][] C = new int[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;
}
}``````
``````public class Solution {
public int[][] multiply(int[][] A, int[][] B) {
if (A == null || A.length == 0 || B == null || B.length == 0) return new int[0][0];
if (A[0].length != B.length) return new int[0][0];

int m = A.length;
int n = A[0].length;
int nB = B[0].length;

int[][] res = new int[m][nB];

for (int i=0; i<m; i++) {
for (int k=0; k<n; k++) {
if (A[i][k] != 0) {
for (int j=0; j<nB; j++) {
if (B[k][j] != 0) res[i][j] += A[i][k]*B[k][j];
}
}
}
}

return res;
}
}``````
``````public class Solution {

public int[][] multiply(int[][] A, int[][] B) {
int m = A.length, n = A[0].length, nB = B[0].length;
int[][] result = new int[m][nB];

List[] indexA = new List[m];
for(int i = 0; i < m; i++) {
List<Integer> numsA = new ArrayList<>();
for(int j = 0; j < n; j++) {
if(A[i][j] != 0){
}
}
indexA[i] = numsA;
}

for(int i = 0; i < m; i++) {
List<Integer> numsA = indexA[i];
for(int p = 0; p < numsA.size() - 1; p += 2) {
int colA = numsA.get(p);
int valA = numsA.get(p + 1);
for(int j = 0; j < nB; j ++) {
int valB = B[colA][j];
result[i][j] += valA * valB;
}
}
}

return result;
}
}``````