讨论/《哈希表》 - 稀疏矩阵的乘法/
《哈希表》 - 稀疏矩阵的乘法

感觉官方应该给一个解答才是 这题没太看明白 hashmap 怎么样用才好?

class Solution:
    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        m, k, n = len(mat1), len(mat1[0]), len(mat2[0])
        ans = [[0] * n for _ in range(m)]

        sparse_A = self.get_none_zero(mat1)
        sparse_B = self.get_none_zero(mat2)

        for i, j, val_A in sparse_A:
            for x, y, val_B in sparse_B:
                if j == x:
                    ans[i][y] += val_A * val_B

        # # Brute Force solution
        # for i in range(m):
        #     for j in range(n):
        #         for t in range(k):
        #             ans[i][j] += mat1[i][t] * mat2[t][j]

        return ans

    def get_none_zero(self, A):
        res = []
        n, m = len(A), len(A[0])
        for i in range(n):
            for j in range(m):
                if A[i][j] == 0:
                    continue
                res.append((i, j, A[i][j]))
        return res