*311. Sparse Matrix Multiplication

https://leetcode.com/problems/sparse-matrix-multiplication/

solution

• Brute Force

class Solution(object):
    def multiply(self, mat1, mat2):
        m = len(mat1)
        n = len(mat2)
        l = len(mat2[0])
        ans = [[0] * l for _ in range(m)]
        for i in range(m):
            for j in range(l):
                for k in range(n):
                    ans[i][j] += mat1[i][k] * mat2[k][j]
        return ans

时间复杂度：O(mnl) 空间复杂度：O(nl)

• hash

# https://zhuanlan.zhihu.com/p/595939499

class Solution(object):
    def multiply(self, mat1, mat2):
        m = len(mat1)
        k = len(mat1[0])
        n = len(mat2[0])

        # create sparse matrix
        h1 = {}
        for i in range(m):
            for j in range(k):
                if mat1[i][j] != 0:
                    if j not in h1:
                        h1[j] = []
                    h1[j].append([i, mat1[i][j]])

        h2 = {}
        for j in range(k):
            for p in range(n):
                if mat2[j][p] != 0:
                    if j not in h2:
                        h2[j] = []
                    h2[j].append([p, mat2[j][p]])

        res = [[0] * n for _ in range(m)]
        for j in h1:
            for i, v1 in h1[j]:
                for p, v2 in h2.get(j, []):
                    res[i][p] += v1 * v2
        return res

时间复杂度：O() 空间复杂度：O()