首页 > 试题广场 >

矩阵乘法

[编程题]矩阵乘法

热度指数：6280 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $1 \le n \le 100$ ， $-100 \le Matrix_{i,j}\le 100$

要求：空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^3 )$

进阶：本题也有空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^{log7})$ 的解法

PS：更优时间复杂度的算法这里并不考察

示例1

输入

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

输出

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

示例2

输入

[[1]],[[1]]

输出

[[1]]

算法知识视频讲解

牛客516598323号

不能用numpy难受啊

import numpy as np
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param a int整型二维数组 第一个矩阵
# @param b int整型二维数组 第二个矩阵
# @return int整型二维数组
#
class Solution:
    def solve(self, a, b):
        # write code here
        a = np.array(a)
        b = np.array(b)
        r = np.dot(a, b)
        return r.tolist()

官方参考答案

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)
    {
        if (a.size() == 0)
            return {};

        vector<vector<int>> ret(a.size(), vector<int>(a.size(), 0));
        for (int i = 0; i < a.size(); ++i)
        {
            for (int j = 0; j < a.size(); ++j)
            {
                for (int k = 0; k < a.size(); ++k)
                    ret[i][j] += (a[i][k] * b[k][j]);
            }
        }

        return ret;
    }
};

编辑于 2020-10-21 10:55:31 回复(1)

Java

牛客839384289号

public int[][] solve (int[][] a, int[][] b) {
    // write code here
    int m=a.length;
    int[][] res=new int[m][m];
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                res[i][k]+=a[i][j]*b[j][k];
            }
        }
    }
    return res;
}

编辑于 2024-03-17 13:39:01 回复(0)

梅子酒l

一般情况下的矩阵相乘，记录下，不针对本题

def transpose(num):
    m = len(num)
    n = len(num[0])
    dp = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(m):
        for j in range(n):
            dp[j][i] = num[i][j]
    return dp

def suan(m,n):
    value = 0
    for i in range(len(m)):
        value += m[i]*n[i]
    return value

s = list(map(int,input().split(',')))
x,y,z = s[0],s[1],s[2]
num1 = []
num2 = []
num = [[0 for _ in range(z)] for _ in range(x)]
for _ in range(x):
    num1.append(list(map(int, input().split(','))))
for _ in range(y):
    num2.append(list(map(int, input().split(','))))
num2 = transpose(num2)
for i in range(x):
    for j in range(z):
        num[i][j] = suan(num1[i], num2[j])
print(num)

发表于 2022-09-13 16:46:40 回复(0)

饥饿的懒羊羊在刷题

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a int整型二维数组 第一个矩阵
     * @param b int整型二维数组 第二个矩阵
     * @return int整型二维数组
     */
    public int[][] solve (int[][] a, int[][] b) {
        // write code here
         int[][] res = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < a[0].length; k++) {
                    res[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return res;
    
    }
}

发表于 2022-06-08 20:43:01 回复(0)

Java

世界杯2009

支持：MXN矩阵乘以NXP矩阵=MXP

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param a int整型二维数组 第一个矩阵
     * @param b int整型二维数组 第二个矩阵
     * @return int整型二维数组
     */
    public int[][] solve(int[][] a, int[][] b) {
        // write code here
        // 矩阵乘法等于矩阵行乘矩阵列
        // mXn矩阵乘nXp矩阵=mXp矩阵
        int[][] res = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                for (int k = 0; k < b[j].length; k++) {
                    res[i][k] += a[i][j] * b[j][k];
                }
            }
        }
        return res;
    }
}

发表于 2022-04-16 22:34:25 回复(0)

Python3

Oo啊哈

class Solution:
    def solve(self , a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
        # write code here
        res = [[0]*len(b[0]) for i in range(len(a))]
        for i in range(len(a)):
            for j in range(len(b[0])):
                for k in range(len(b)):
                    res[i][j] += a[i][k]*b[k][j]
        return res

发表于 2022-04-09 20:09:04 回复(0)

牛客977941825号

class Solution:
def solve(self , a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
# write code here
ans = [[]for i in range(0,len(a))]
i = 0
j = 0
k = 0
m = len(a)
p = len(a[0])
n = len(b[0])

for i in range(0,m):
for j in range(0,n):
t = 0
for k in range(0,p):
t += a[i][k] * b[k][j]
ans[i].append(t)
return ans

发表于 2022-01-28 20:23:46 回复(0)

Java

菲尼克斯弗兰克

public int[][] solve (int[][] a, int[][] b) {
    int n = a.length;
    int[][] res = new int[n][n];
    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;
}

发表于 2022-01-23 12:11:04 回复(0)

Java

惠灵顿靖

import java.util.*;
//六刷
public class Solution {

    public int[][] solve (int[][] a, int[][] b) {
        int len=a.length;
        if (len == 0) return null;
        int[][] res = new int[len][len];
        
//         boolean flag=true;
//         for (int row = 0; row < len; row++) {
//             for (int col = 0; col < len; col++) {
//                 if(a[row][col]!=0){
//                     flag=false;
//                     break;
//                 }
//             }
//         }
//         if(flag==true)return a;
        
        for (int row = 0; row < len; row++) {
            for (int col = 0; col < len; col++) {
                res[row][col] = matrixMul(a, b, row, col);
            }
        }
        return res;
    }

    // 第一个矩阵 i 行和第二个矩阵 j 列的乘积
    public int matrixMul (int[][] a, int[][] b, int row, int col) {
        int result = 0;
        int le=a.length;
        for (int k = 0; k < le; k++) {
            result += a[row][k] * b[k][col];
        }
        return result;
    }
}

发表于 2021-10-01 17:34:21 回复(0)

C++

海饼干666

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
        if(a.size() == 0) return{};
        if(a[0].size() != b.size()) return{};
        vector<vector<int> > Result(a.size(),vector<int>(b[0].size(),0));
        for(int i = 0; i < a.size(); i++)
        {
            for(int j = 0; j < b[0].size(); j++)
            {
                int sum = 0;
                for(int k = 0; k < b.size(); k++)
                {
                    sum += a[i][k]*b[k][j];
                }
                Result[i][j] = sum;
            }
        }
        return Result;
    }
};

发表于 2021-08-27 09:54:43 回复(0)

Java

我是阿落落落

题解里数组读取顺序的优化也超时啊，有人解决了吗？

发表于 2021-08-13 00:28:46 回复(0)

Java

maple201809041428901

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a int整型二维数组 第一个矩阵
     * @param b int整型二维数组 第二个矩阵
     * @return int整型二维数组
     */
    public int[][] solve (int[][] a, int[][] b) {
        // write code here
        // [1,2     [1,2
        //  3,4] *   3,4]
        int n = a.length;
        int[][] ans = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < n; k++) {
                    ans[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return ans;
    }
}

发表于 2021-07-31 17:36:40 回复(0)

发个offer就摆烂

不适用numpy,用三元表达式：

func = lambda x,y : x*y

map(fuc, arrA, arrB)

class Solution:
    def solve(self , a , b ):
        # write code here
        n = len(a)
        dat = [[0]*n for _ in range(n)]
        func = lambda x,y : x*y
        for i,val in enumerate(a):
            time = 0
            k = 0
            while time<len(b):
                value = []
                for j in range(len(b)):
                    value.append(b[j][k])
                dat[i][time] = sum(list(map(func, val, value)))
                time += 1
                k += 1
        return dat

发表于 2021-06-19 21:12:37 回复(0)

乌龟办走读，鳖不住校了

class Solution {
public:
    vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
    // write code here
    //矩阵能够相乘的前提是前面矩阵的列数和后面矩阵的行数相同，如果不同的话不能相乘
    vector<vector<int>>res;
    vector<int>ans;
    if(a[0].size()!=b.size())return res;//无法相乘
    int temp=0;
    for(int m=0;m<a.size();m++)//每一行循环完之后将ans容器放进res容器中
    {
       for(int n=0;n<b[0].size();n++)
         {
           for(int i=0;i<a[0].size();i++)
            {
              temp+=a[m][i]*b[i][n];//这里是乘法
              //因为是同时进行的，对应位置同时相乘，不能嵌套循环

            }      
              ans.push_back(temp);
              temp=0;//矩阵当前元素存入之后要清零，以防后面继续累加
         }

             res.push_back(ans);
              ans.clear();//和temp清零一样，以防积累效应
    }
    return res;
   }
};

发表于 2021-06-17 10:58:07 回复(0)

Java

花落梦里

    public int[][] solve (int[][] a, int[][] b) {
        int n=a.length;
        int[][]res=new int[n][n];
        for(int x=0;x<n;x++){
            for(int y=0;y<n;y++){
                int sum=0;
                for(int i=0;i<n;i++){
                  sum+=(a[x][i]*b[i][y]);
                    
                }
                res[x][y]=sum;
            }
        }
        return res;
    }

发表于 2021-03-27 10:26:53 回复(0)

Python

猫牛

class Solution:
    def solve(self , a , b ):
        # write code here
        m, k, n = len(a), len(a[0]), len(b[0])
        res = [[0 for _ in range(n)] for _ in range(m)]
        # res[i][j] = sum()
        for i in range(m):
            for j in range(n):
                res[i][j] = sum(x * y for x, y in zip(a[i], [r[j] for r in b]))
                
        return res

发表于 2021-03-19 01:26:24 回复(0)

Python

DanicaWong

class Solution:
    def solve(self , a , b ):
        # write code here
        length = len(a)
        matrix = [[0 for j in range(length)] for i in range(length)]
        for i in range(length):
            for j in range(length):
                for m in range(length):
                    matrix[i][j] += a[i][m] * b[m][j]
        return matrix

编辑于 2021-02-04 13:52:20 回复(1)

ponmmains

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param a int整型二维数组第一个矩阵
* @param b int整型二维数组第二个矩阵
* @return int整型二维数组
*/
public int[][] solve (int[][] a, int[][] b) {
// write code here
if (a == null || b == null)
return null;

for (int i = 0; i < a.length; i++) {
for (int j = 0; j <= i; j++) {
int tmp = b[i][j];
b[i][j] = b[j][i];
b[j][i] = tmp;
}
}

int[][] ans = new int[a.length][a.length];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
ans[i][j] = calculation(a[i], b[j]);
}
}

return ans;
}

private int calculation(int[] row, int[] col) {
int sum = 0;
for (int i = 0; i < row.length; i++) {
sum += row[i] * col[i];
}

return sum;
}

}

发表于 2021-01-24 17:27:39 回复(0)

JavaScript

别卷啦！

function solve( a ,  b ) {
    // write code here
    let m = a.length
    let matrix = Array.from(new Array(m), ()=> new Array(m).fill(0)) 
    for(let i = 0 ;i<m; i++){
        for(let j = 0;j<m; j++){
            for(let k =0;k<m; k++ ){
               matrix[i][j] += a[i][k]* b[k][j]  
            }
        }
    }
    return matrix
}

发表于 2021-01-12 12:22:56 回复(0)

Java

百度专业内推官

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a int整型二维数组 第一个矩阵
     * @param b int整型二维数组 第二个矩阵
     * @return int整型二维数组
     */
    public int[][] solve (int[][] a, int[][] b) {
        if (a.length == 0 || b.length == 0) return null;

        int[][] res = new int[a.length][a[0].length];
        for (int row = 0; row < a.length; row++) {
            for (int col = 0; col < a[0].length; col++) {
                res[row][col] = matrixMul(a, b, row, col);
            }
        }
        return res;
    }

    // 第一个矩阵 i 行和第二个矩阵 j 列的乘积
    public int matrixMul (int[][] a, int[][] b, int row, int col) {
        int result = 0;
        for (int k = 0; k < a.length; k++) {
            result += a[row][k] * b[k][col];
        }
        return result;
    }
}

发表于 2020-12-20 19:25:10 回复(1)