[leetcode]Sparse Matrix Multiplication

加了个0 row col才过 不知道有没有更快的方法

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

public class Solution { public int[][] multiply(int[][] A, int[][] B) { if (A.length == 0 || B.length == 0 || A[0].length != B.length) return null; int result[][] = new int[A.length][B[0].length]; HashSet<Integer> zeroRow = new HashSet<Integer>(); HashSet<Integer> zeroCol = new HashSet<Integer>(); for (int i = 0; i < A.length; i++){ for (int j = 0; j < B[0].length; j++){ if (!(zeroRow.contains(i) || zeroCol.contains(j))){ int sum = 0; boolean rowZero = false; boolean colZero = false; for (int k = 0; k < A[i].length; k++){ sum += A[i][k]*B[k][j]; rowZero = rowZero & A[i][k] == 0; colZero = colZero & B[k][j] == 0; } result[i][j] = sum; if (rowZero) zeroRow.add(i); if (colZero) zeroCol.add(j); } } } return result; } }