题目地址：https://leetcode-cn.com/problems/sparse-matrix-multiplication/
题目描述
Given two sparse matrices A and B, return the result of AB.
Youmay assume that A's column number is equal to B's row number.
Example:
Input:
A = [
[ 1, 0, 0],
[-1, 0, 3]
]
B = [
[ 7, 0, 0 ],
[ 0, 0, 0 ],
[ 0, 0, 1 ]
]
Output:
| 1 0 0 | | 7 0 0 | | 7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
| 0 0 1 |
题目大意
给定两个 稀疏矩阵 A 和 B，请你返回 AB。你可以默认 A 的列数等于 B 的行数。
解题方法
暴力
直接按照矩阵乘法，可以暴力求解。矩阵乘法是三重循环，时间复杂度是O(N^3)。
【图片失效】
题目给的系数矩阵的特征怎么用呢？可以考虑先遍历一次两个矩阵，记录下A的行和B的列全部为0的索引，当遍历到这些索引时，直接给res中填入0。下面的代码没有这么做，也能通过。
C++代码如下：
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
if (A.empty() || A[0].empty() || B.empty() || B[0].empty()) return vector<vector<int>>();
int M = A.size();
int N = B[0].size();
vector<vector<int>> res(M, vector<int>(N, 0));
for (int row = 0; row < M; ++row) {
for (int col = 0; col < N; ++col) {
int cur = 0;
for (int i = 0; i < A[0].size(); ++i) {
cur += A[row][i] * B[i][col];
}
res[row][col] = cur;
}
}
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
科学计算库numpy
Python有科学计算库numpy可以使用，直接使用库函数求得矩阵的乘法。
import numpy as np
class Solution(object):
def multiply(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
a = np.array(A)
b = np.array(B)
return np.matmul(a, b)
1 2 3 4 5 6 7 8 9 10 11
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发