Сложность: medium
Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно.
Пример:
Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]
👨💻 Алгоритм:
1⃣Инициализация результирующей матрицы
Создайте результирующую матрицу result размером m x n, заполненную нулями.
2⃣Хранение ненулевых элементов
Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map.
3⃣Вычисление произведения
Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j].
😎 Решение:
class Solution:
def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
n = len(mat1)
k = len(mat1[0])
m = len(mat2[0])
ans = [[0] * m for _ in range(n)]
for rowIndex in range(n):
for elementIndex in range(k):
if mat1[rowIndex][elementIndex] != 0:
for colIndex in range(m):
ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex]
return ans
Ставь 👍 и забирай 📚 Базу знаний