矩阵乘法

[编程题]矩阵乘法

热度指数：6307 时间限制：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]]

算法知识视频讲解

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)

Python

牛客247812159号

我自己测重复五次10*10还不到0.1ms，感觉挺快的了，调试怎么都说超时

class Solution: def solve(self , a , b ):
        c = []  for i in range(len(a)):  for j in range(len(a)):
                c.append(int(sum([a[i][n] * b[n][j] for n in range(len(a))])))  return ([c[k*len(a):(k*len(a)+len(a))] for k in range(len(a))])