# Sparse Matrix Multiplication

Given two [sparse matrices](https://en.wikipedia.org/wiki/Sparse_matrix) **A** and **B**, return the result of **AB**.

You may assume that **A**'s column number is equal to **B**'s row number.

**Example:**

```
A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]


     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |
```

这道题让我们实现稀疏矩阵相乘，稀疏矩阵的特点是矩阵中绝大多数的元素为0，而相乘的结果是还应该是稀疏矩阵，即还是大多数元素为0，那么我们使用传统的矩阵相乘的算法肯定会处理大量的0乘0的无用功，所以我们需要适当的优化算法，使其可以顺利通过OJ，我们知道一个 i x k 的矩阵A乘以一个 k x j 的矩阵B会得到一个 i x j 大小的矩阵C，那么我们来看结果矩阵中的某个元素C\[i]\[j]是怎么来的，起始是A\[i]\[0]\*B\[0]\[j] + A\[i]\[1]\*B\[1]\[j] + ... + A\[i]\[k]\*B\[k]\[j]，那么为了不重复计算0乘0，我们首先遍历A数组，要确保A\[i]\[k]不为0，才继续计算，然后我们遍历B矩阵的第k行，如果B\[K]\[J]不为0，我们累加结果矩阵res\[i]\[j] += A\[i]\[k] \*B\[k]\[j]; 这样我们就能高效的算出稀疏矩阵的乘法

```
class Solution(object):
    def multiply(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
        result = [[0]*len(B[0]) for _ in xrange(len(A))]
        for i in xrange(len(A)):
            for j in xrange(len(A[0])):
                if A[i][j] != 0:
                    for k in xrange(len(B[0])):
                        if B[j][k] != 0:
                            result[i][k] += A[i][j]*B[j][k]
        return result
```

注意初始化result的写法


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://rachel2011.gitbook.io/leetcode_cc150/leetcode/sparse-matrix-multiplication.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.