数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++稀疏矩阵乘法
假设我们有两个矩阵 A 和 B，我们需要找到 AB 的结果。我们可以假设 A 的列数等于 B 的行数。
所以，如果输入类似于 [[1,0,0],[-1,0,3]] [[7,0,0],[0,0,0],[0,0,1]]，
| 1 | 0 | 0 |
| -1 | 0 | 3 |
| 7 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 1 |
那么输出将是 [[7,0,0],[-7,0,3]]
| 7 | 0 | 0 |
| -7 | 0 | 3 |
为了解决这个问题，我们将遵循以下步骤：
r1 := A 的大小，r2 := B 的大小
c1 := A[0] 的大小，c2 := B[0] 的大小
定义一个 r1 x c2 阶的二维数组 ret
定义一个包含 pair 的数组 sparseA[r1]
初始化 i := 0，当 i < r1 时，更新（i 加 1），执行：
初始化 j := 0，当 j < c1 时，更新（j 加 1），执行：
如果 A[i, j] 不等于 0，则：
将 { j, A[i, j] } 插入 sparseA[i] 的末尾
初始化 i := 0，当 i < r1 时，更新（i 加 1），执行：
初始化 j := 0，当 j < sparseA[i] 的大小，更新（j 加 1），执行：
初始化 k := 0，当 k < c2 时，更新（k 加 1），执行：
x := sparseA[i, j] 的第一个元素
如果 B[x, k] 不等于 0，则：
ret[i, k] := ret[i, k] + sparseA[i, j] 的第二个元素 * B[x, k]
返回 ret
示例
让我们来看下面的实现来更好地理解：
class Solution {
public:
vector<vector<int<> multiply(vector<vector<int<>& A, vector<vector<int<>& B) {
int r1 = A.size();
int r2 = B.size();
int c1 = A[0].size();
int c2 = B[0].size();
vector < vector <int< > ret(r1, vector <int< (c2));
vector < pair <int, int> > sparseA[r1];
for(int i = 0; i < r1; i++){
for(int j = 0; j < c1; j++){
if(A[i][j] != 0)sparseA[i].push_back({j, A[i][j]});
}
}
for(int i = 0; i < r1; i++){
for(int j = 0; j < sparseA[i].size(); j++){
for(int k = 0; k < c2; k++){
int x = sparseA[i][j].first;
if(B[x][k] != 0){
ret[i][k] += sparseA[i][j].second * B[x][k];
}
}
}
}
return ret;
}
};输入
{{1,0,0},{-1,0,3}},{{7,0,0},{0,0,0},{0,0,1}}输出
[[7, 0, 0, ],[-7, 0, 3, ],]
更新于：2020年11月18日
2K+ 次浏览
广告