[LeetCode]Sparse Matrix Multiplication

稀疏矩阵相乘的问题，假设A矩阵为m * n，B矩阵为n * k，那么输出矩阵为m * k，并且求每一个元素的实际那复杂度是O(n)，总的时间复杂度就是O(m * n * k)。但是既然题目说了是稀疏矩阵，那么我们可以免去很多不必要的计算。比如，对于A矩阵，我们就可以把其转化为Hashmap of hashmap，只存不为0的数的索引，我们只需要遍历hashmap每一行对应的不为0的元素然后去B中找对应的元素相乘累加到对应的位置即可。假设A中每行不为0的元素平均数量为d，d肯定远小于n，那么时间复杂度为O(m * d * k)，空间复杂度O(m * d), 代码如下：




我们还有一种不用额外空间的方法。对于A中的某个元素A[i][j]，其只可能分别和B[j][0->k]的乘积累加到C[i][0->k]中，所以我们只需要在遍历A的每个不为0的元素的时候，不断更新C即可。时间复杂度为O(m * d * k)，常数空间，代码如下：