边工作边刷题：70天一遍leetcode: day 91

Sparse Matrix Multiplication

要点：

用hashmap与brute force的不同：显然brute force是O(mnk)，因为是稀疏矩阵，所以用了hashmap可以把k降到很小。
最终的计算还是2d loop m和n，只是loop k时候，变成找对应n的list，而不用所有k个。所以Bmap[n][k]。
(optional) 当然，这题也不一定用hashmap，可以内层loop k，因为k中非available的元素对应的j循环都被过滤掉了，所以实际上*n的数量只有available的k。所以复杂度是类似的。最内层j的循环实际上是分别累加到m[i][j]上。https://discuss.leetcode.com/topic/40297/is-there-a-real-need-of-a-hashmap-for-this-problem/2

构建Bmap的时候，用虽然Bmap为[n][k]，对应的B[k][n]
和m/n的长度无关，所以没有优化


# Given two sparse matrices A and B, return the result of AB.

# You may assume that A's column number is equal to B's row number.

# Example:

# A = [
#   [ 1, 0, 0],
#   [-1, 0, 3]
# ]

# B = [
#   [ 7, 0, 0 ],
#   [ 0, 0, 0 ],
#   [ 0, 0, 1 ]
# ]


#      |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
# AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
#                   | 0 0 1 |


class Solution(object):
    def multiply(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
        m,k,n = len(A), len(B), len(B[0])
        # if m>n: # error: has nothing to do with m,n size
        #     A,B=B,A
        #     m,n=n,m
        
        Bmap = [[] for _ in xrange(n)] # error: Bmap should be n
        for x in xrange(n):
            for y in xrange(k):
                if B[y][x]!=0: # error: for B, it's y,x not x,y
                    Bmap[x].append(y)
        
        res = [[0]*n for _ in xrange(m)]
        for x in xrange(m):
            for y in xrange(n):
                for k in Bmap[y]:
                    if A[x][k]!=0:
                        res[x][y]+=A[x][k]*B[k][y]
        
        return res
        
sol = Solution()
assert sol.multiply([[1,0,0],[-1,0,3]], [[7,0,0],[0,0,0],[0,0,1]])==[[7,0,0],[-7,0,3]], "must be [[7,0,0],[-7,0,3]]"
assert sol.multiply([[1,-5]], [[12],[-1]])==[[17]], "must be [[17]]"