题解 | #矩阵乘法#

思路：

题目的主要信息：

• 求两个矩阵相乘结果，两个矩阵一定存在，不用排除特殊情况
• 两个矩阵都为的矩阵

方法一：暴力法
具体做法：
直接遍历二维矩阵的每个元素，其中等于a b两个矩阵的行乘列叠加即可。

class Solution {
public:
    vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
        int n = a.size(); 
        vector<vector<int> > res(n, vector<int>(n, 0)); //构建结果矩阵
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                    res[i][j] += a[i][k] * b[k][j]; //行*列相加
         return res;
    }
};

复杂度分析：

• 时间复杂度：，三层循环
• 空间复杂度：，res是必要空间，不属于额外空间

方法二：暴力法缓存优化
具体做法：
调换代码顺序，依据cpu连续读取的特性，优先访问a[i][k]，利用更多的空间连续性，虽然时间复杂度没有变，但是可以节省更多时间。

class Solution {
public:
    vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
        int n = a.size();
        int temp;
        vector<vector<int> > res(n, vector<int>(n, 0)); //构建结果矩阵
        for(int i = 0; i < n; i++)
            for(int k = 0; k < n; k++){
                temp = a[i][k];  //优先访问这个
                for(int j = 0; j < n; j++)
                    res[i][j] += temp * b[k][j]; //行*列相加
            }
         return res;
    }
};

复杂度分析：

• 时间复杂度：，三层循环
• 空间复杂度：，res是必要空间，不属于额外空间