这个题目考点在于矩阵中有很多0的时候怎么处理。我是创建了一个Node的数据结构，分别存index和值。看网上有个小哥是把index和值分别存在 i 和i + 1 的位置，感觉也很好，不过算法复杂度本质没有变化。
public class Solution { public int[][] multiply(int[][] A, int[][] B) { int row_A = A.length; int col_A = A[0].length; int row_B = B.length; int col_B = B[0].length; int[][] result = new int[row_A][col_B]; for (int r = 0; r < row_A; r++) { List<Node> list = new ArrayList<Node>(); for (int c = 0; c < col_A; c++) { if (A[r][c] != 0) { list.add(new Node(c, A[r][c])); } } for (int c = 0; c < col_B; c++) { result[r][c] = helper(list, B, c); } } return result; } public int helper(List<Node> A, int[][] B, int c) { int result = 0; for (Node node : A) { result += node.val * B[node.ind][c]; } return result; } class Node { int ind; int val; public Node(int ind, int val) { this.ind = ind; this.val = val; } } }
后来还是写了一下，因为发现我的要300ms。这样来说同样的复杂度，多调用一个类和一个helper函数还是会很影响速度的。代码如下，大概只需要100ms
public class Solution { public int[][] multiply(int[][] A, int[][] B) { int row_A = A.length; int col_A = A[0].length; int row_B = B.length; int col_B = B[0].length; int[][] result = new int[row_A][col_B]; for (int r = 0; r < row_A; r++) { List<Integer> list = new ArrayList<Integer>(); for (int c = 0; c < col_A; c++) { if (A[r][c] != 0) { list.add(c); list.add(A[r][c]); } } for (int c = 0; c < col_B; c++) { int tmp = 0; for (int i = 0; i < list.size(); i += 2) { tmp += list.get(i + 1) * B[list.get(i)][c]; } result[r][c] =tmp; } } return result; } }
[LeedCode]Sparse Matrix Multiplication
原文：http://www.cnblogs.com/vision-love-programming/p/5002131.html