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