LeetCode 311. 稀疏矩阵的乘法

Categories:

题目描述
思路分析
1. 解法一：仅遍历非零元素（推荐）
相似题目

题目描述

✅ 311. 稀疏矩阵的乘法

思路分析

解法一：仅遍历非零元素（推荐）

核心思路：

对矩阵 A 按行存储非零元素 (col, val)。

对矩阵 B 按行存储非零元素 (col, val)（用于匹配 A 的列）。

当 A 的 (i, k) 与 B 的 (k, j) 都非零时，累加到结果 res[i][j]。

复杂度分析：

时间复杂度：O(nnz(A) * avgRowB)，仅与非零元素相关。

空间复杂度：O(nnz(A) + nnz(B))。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        int m = mat1.length;
        int k = mat1[0].length;
        int n = mat2[0].length;

        List<int[]>[] rowsA = new List[m];
        for (int i = 0; i < m; i++) {
            rowsA[i] = new ArrayList<>();
            for (int j = 0; j < k; j++) {
                if (mat1[i][j] != 0) {
                    rowsA[i].add(new int[]{j, mat1[i][j]});
                }
            }
        }

        List<int[]>[] rowsB = new List[k];
        for (int i = 0; i < k; i++) {
            rowsB[i] = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (mat2[i][j] != 0) {
                    rowsB[i].add(new int[]{j, mat2[i][j]});
                }
            }
        }

        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int[] a : rowsA[i]) {
                int colA = a[0];
                int valA = a[1];

                for (int[] b : rowsB[colA]) {
                    int colB = b[0];
                    int valB = b[1];
                    res[i][colB] += valA * valB;
                }
            }
        }

        return res;
    }
}

type pair311 struct {
	idx int
	val int
}

func multiply(mat1 [][]int, mat2 [][]int) [][]int {
	m, k := len(mat1), len(mat1[0])
	n := len(mat2[0])

	rowsA := make([][]pair311, m)
	for i := 0; i < m; i++ {
		for j := 0; j < k; j++ {
			if mat1[i][j] != 0 {
				rowsA[i] = append(rowsA[i], pair311{idx: j, val: mat1[i][j]})
			}
		}
	}

	rowsB := make([][]pair311, k)
	for i := 0; i < k; i++ {
		for j := 0; j < n; j++ {
			if mat2[i][j] != 0 {
				rowsB[i] = append(rowsB[i], pair311{idx: j, val: mat2[i][j]})
			}
		}
	}

	res := make([][]int, m)
	for i := 0; i < m; i++ {
		res[i] = make([]int, n)
		for _, a := range rowsA[i] {
			for _, b := range rowsB[a.idx] {
				res[i][b.idx] += a.val * b.val
			}
		}
	}

	return res
}

相似题目

题目	难度	考察点
311. 稀疏矩阵的乘法	中等	矩阵、稀疏
566. 重塑矩阵	简单	矩阵遍历
48. 旋转图像	中等	矩阵操作
73. 矩阵置零	中等	矩阵遍历
867. 转置矩阵	简单	矩阵遍历
1424. 对角线遍历 II	中等	矩阵遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/37869182