难度: Medium
Submission
运行时间: 23 ms
内存: 16.5 MB
from typing import List
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
m, k = len(mat1), len(mat1[0])
n = len(mat2[0])
# 创建一个大小为 m x n 的结果矩阵，初始化为全零
result = [[0] * n for _ in range(m)]
# 遍历 mat1 的每个元素
for i in range(m):
for j in range(k):
if mat1[i][j] != 0:
# 遍历 mat2 的每个元素
for l in range(n):
if mat2[j][l] != 0:
# 计算乘积并加到结果矩阵的对应位置
result[i][l] += mat1[i][j] * mat2[j][l]
return result
Explain
这个解法利用了稀疏矩阵的特性，即矩阵中大部分元素为0。通过只处理非零元素，可以提高算法的效率。算法首先确定了结果矩阵 result 的尺寸为 m x n，并初始化为全零。之后，算法遍历矩阵 mat1 中的每一个元素，如果 mat1 的元素不为零，则继续遍历矩阵 mat2 的对应行。对于 mat2 中的每一个不为零的元素，计算乘积并累加到结果矩阵 result 的相应位置。这种方法有效地减少了不必要的计算，尤其是避免了与零的乘法。
时间复杂度: O(A*B)
空间复杂度: O(m*n)
from typing import List
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
m, k = len(mat1), len(mat1[0])
n = len(mat2[0])
# 创建一个大小为 m x n 的结果矩阵，初始化为全零
result = [[0] * n for _ in range(m)]
# 遍历 mat1 的每个元素
for i in range(m):
for j in range(k):
if mat1[i][j] != 0:
# 遍历 mat2 的每个元素
for l in range(n):
if mat2[j][l] != 0:
# 计算乘积并加到结果矩阵的对应位置
result[i][l] += mat1[i][j] * mat2[j][l]
return result
Explore
在实现稀疏矩阵乘法时，通过简单的条件检查来确定哪些元素是非零的。具体地，算法遍历矩阵 mat1 的每个元素，使用条件语句 `if mat1[i][j] != 0` 来判断元素是否非零。如果是非零，再进一步处理；同样的逻辑应用于矩阵 mat2，在内层循环中使用 `if mat2[j][l] != 0` 来检查。这样的处理确保只有当两个矩阵的对应元素均非零时，才执行乘法和加法操作。
这个算法的实现假设了 mat2 至少有一列，即 `n = len(mat2[0])` 至少为1。如果 mat2 没有列（即列数为零），直接访问 `mat2[0]` 将会引发索引错误。在实际应用中，应该先检查 mat2 是否至少含有一列，否则应该返回一个与 mat1 行数相同、但列数为零的结果矩阵。
是的，这种方法特别适用于那些维度大但非零元素极少的稀疏矩阵。因为算法只处理非零元素，所以计算量主要取决于非零元素的数量而非矩阵的总体尺寸。这样可以显著减少不必要的计算，尤其是避免了大量的零乘法操作，从而使得算法在处理大规模稀疏矩阵时更加高效。
这是一种可行的优化手段。通过预先构建一个数据结构（如字典或列表）来存储 mat2 中每列的非零元素和它们的索引，可以进一步减少遍历次数。在遍历 mat1 时，可以直接访问这个数据结构，快速获取 mat2 的非零元素，从而减少对 mat2 全部元素的重复检查，特别是在 mat2 的非零元素分布极不均匀时，这种优化可以提高效率。