列表

详情


NC143. 矩阵乘法

描述

给定两个 n*n 的矩阵 A 和 B ,求 A*B 。

数据范围:

要求:空间复杂度 , 时间复杂度
进阶:本题也有空间复杂度 ,时间复杂度 的解法
PS:更优时间复杂度的算法这里并不考察

示例1

输入:

[[1,2],[3,2]],[[3,4],[2,1]]

输出:

[[7,6],[13,14]]

示例2

输入:

[[1]],[[1]]

输出:

[[1]]

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 5ms, 内存消耗: 660KB, 提交时间: 2021-08-05

class Solution {
public:
    vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
        int n = a.size(); // 记录矩阵的大小
        int res; // 记录结果
        vector<vector<int> > ans(n, vector<int>(n)); //用于存储结果
        for(int i = 0; i < n; i++)
            for(int k = 0; k < n; k++)
            {
                res = a[i][k]; // 进行空间层次的优化
                for(int j = 0; j < n; j++)
                {
                    ans[i][j] += res * b[k][j]; //行列元素对应相乘后相加
                }
            }
         return ans; // 返回结果
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 664KB, 提交时间: 2021-08-03

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) {
        // write code here
        int a_row = a.size(), a_col = a[0].size();
        int b_row = b.size(), b_col = b[0].size();
        
        vector<vector<int> > out(a_row, vector<int>(b_col, 0));
        for(int k = 0; k < a_col; k++) {
        for(int i = 0; i < a_row; i++) {
            for(int j = 0; j < b_col; j++) {
                
                    out[i][j] += (a[i][k] * b[k][j]);
                }
            }
        }
        
        return out;
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 680KB, 提交时间: 2021-08-03

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) {
        // write code here
        int m = a.size();//A的行数
            int p = a[0].size();//A的列数=B的行数
            int n = b[0].size();//B的行数
            vector<vector<int>> ans(m);
            for(int i = 0 ; i < m ; i++)
            {
                for(int j = 0 ; j < n ; j++)
                {
                        int t = 0;
                        for(int k = 0 ; k < p ; k++)
                        {
                                t+=a[i][k]*b[k][j];
                        }
                        ans[i].push_back(t);
                }
            }
            return ans;
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 688KB, 提交时间: 2021-12-17

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) {
        // write code here
        vector<vector<int>> res(a.size(),vector<int>(a.size(),0));
        for (int i = 0;i<a.size();i++)
        {
            for (int j = 0;j<a.size();j++)
            {
                int tmp = 0;
                for (int k = 0;k<a.size();k++)
                {
                    tmp += (a[i][k] * b[k][j]);
                }
                res[i][j] = tmp;
            }
        }
        return res;
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 788KB, 提交时间: 2021-07-30

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) {
        // write code here
        int n=a.size(),m=a[0].size();
        vector<vector<int> > results;
        if(n==0) return results;
        for(int i=0;i<n;i++){
            vector<int> result;
            for(int k=0;k<n;k++){
                int ans=0;
                for(int j=0;j<m;j++){
                    ans+=a[i][j]*b[j][k];
                }
                result.push_back(ans);
            }
            results.push_back(result);
        }
        return results;
    }
};

上一题