Задача: 311. Sparse Matrix Multiplication
Сложность: 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 {
    function multiply($mat1, $mat2) {
        $n = count($mat1);
        $k = count($mat1[0]);
        $m = count($mat2[0]);
        
        $ans = array_fill(0, $n, array_fill(0, $m, 0));
        
        for ($rowIndex = 0; $rowIndex < $n; $rowIndex++) {
            for ($elementIndex = 0; $elementIndex < $k; $elementIndex++) {
                if ($mat1[$rowIndex][$elementIndex] != 0) {
                    for ($colIndex = 0; $colIndex < $m; $colIndex++) {
                        $ans[$rowIndex][$colIndex] += $mat1[$rowIndex][$elementIndex] * $mat2[$elementIndex][$colIndex];
                    }
                }
            }
        }
        
        return $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний