题解 | #矩阵乘法#

描述
给定两个nxn的矩阵A和B，求AxB。
示例

输入：
[[1,2],[3,2]],[[3,4],[2,1]]
返回值：
[[7,6],[13,14]]

方法一：数学模拟
有两个矩阵：a和b（矩阵实际上就是二维数组）

a矩阵和b矩阵可以做乘法运算必须满足a矩阵的列的数量等于b矩阵的行的数量

运算规则：a的每一行中的数字对应乘以b的每一列的数字把结果相加起来

相乘后的矩阵c行数量等于a矩阵的行数，列数等于b矩阵的列数，因为每次循环都是a的行与b的列,所以最外面两层循环分别是a的行的变化和b的列的变化，而最里面的循环可以是a的列或者是b的行来进行变化，因为a的列和是b的行数量是相等的，这样就可以使用三层循环来解决.

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a int整型vector<vector<>> 第一个矩阵
     * @param b int整型vector<vector<>> 第二个矩阵
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
        //a，b数组的行数和列数相等
        int n=a.size();
        vector<vector<int>>c(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++){
                    c[i][j]+=a[i][k]*b[k][j];
                }
            }
        }return c;
    }
};

复杂度：

• 时间复杂度：有三层循环，
• 空间复杂度：辅助空间为相乘后的矩阵c大小为 ,所以空间复杂度为

方法二：利用二维数组在CPU连续存储优化
显然，方法一中计算时遍历完数组第一行和数组第一列后，计算时会从回退到继续用第一行元素计算，比较费时间，可以利用cpu在遍历二维矩阵是一行一行遍历的特性，先存储，将所有需要用到的地方优先计算上，这样遍历数组时就是遵循数组在内存中的存储顺序进行遍历，节省时间，例如先访问，计算出,然后访问，计算出

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a int整型vector<vector<>> 第一个矩阵
     * @param b int整型vector<vector<>> 第二个矩阵
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
        int n=a.size();
        vector<vector<int>>c(n,vector<int>(n,0));
        for(int i=0;i<n;i++){
            for(int k=0;k<n;k++){
                int t=a[i][k];//先访问a[i][k]
                for(int j=0;j<n;j++){
                    c[i][j]+=t*b[k][j];//先计算出所有需要用到a[i][k]的位置，后面再累加
                }
            }
        }return c;
    }
};

复杂度：

• 时间复杂度：三层循环,
• 空间复杂度：辅助空间为相乘后的矩阵c大小为 ,所以空间复杂度为