#ЛитКод
Задача: 311. Sparse Matrix Multiplication

Даны две разреженные матрицы 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].

😎 Решение:

var multiply = function(mat1, mat2) {
    let n = mat1.length;
    let k = mat1[0].length;
    let m = mat2[0].length;
    
    let ans = Array.from({ length: n }, () => Array(m).fill(0));
    
    for (let rowIndex = 0; rowIndex < n; rowIndex++) {
        for (let elementIndex = 0; elementIndex < k; elementIndex++) {
            if (mat1[rowIndex][elementIndex] !== 0) {
                for (let colIndex = 0; colIndex < m; colIndex++) {
                    ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                }
            }
        }
    }
    
    return ans;
};

👉Новости 👉Платформа