LeetCode 311. 稀疏矩阵的乘法
LeetCode 311. 稀疏矩阵的乘法
Michael阿明
发布于 2020-07-13 16:24:15
发布于 2020-07-13 16:24:15
1. 题目
给你两个 稀疏矩阵 A 和 B，请你返回 AB 的结果。 你可以默认 A 的列数等于 B 的行数。
请仔细阅读下面的示例。
示例：
输入：
A = [
[ 1, 0, 0],
[-1, 0, 3]
]
B = [
[ 7, 0, 0 ],
[ 0, 0, 0 ],
[ 0, 0, 1 ]
]
输出：
| 1 0 0 | | 7 0 0 | | 7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
| 0 0 1 |来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sparse-matrix-multiplication 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 暴力求解
- 3层 for 循环
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> ans(A.size(), vector<int>(B[0].size(), 0));
int i, j, k, sum;
for(i = 0; i < A.size(); ++i)
for(j = 0; j < B[0].size(); ++j)
{
sum = 0;
for(k = 0; k < A[0].size(); ++k)
sum += A[i][k]*B[k][j];
ans[i][j] = sum;
}
return ans;
}
};24 ms 8.4 MB
2.2 选取都不为0的行和列相乘
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<bool> r_all0(A.size(),true);
vector<bool> c_all0(B[0].size(),true);
int i, j, k, sum;
bool flag = false;
for(i = 0; i < A.size(); ++i)
{
flag = false;
for(j = 0; j < A[0].size(); ++j)
{
if(A[i][j])
{
flag = true;
break;
}
}
if(flag)
r_all0[i] = false;
}
for(j = 0; j < B[0].size(); ++j)
{
flag = false;
for(i = 0; i < B.size(); ++i)
{
if(B[i][j])
{
flag = true;
break;
}
}
if(flag)
c_all0[j] = false;
}
vector<vector<int>> ans(A.size(), vector<int>(B[0].size(), 0));
for(i = 0; i < A.size(); ++i)
for(j = 0; j < B[0].size(); ++j)
{
if(r_all0[i] || c_all0[j])
continue;
sum = 0;
for(k = 0; k < A[0].size(); ++k)
sum += A[i][k]*B[k][j];
ans[i][j] = sum;
}
return ans;
}
};8 ms 8.6 MB
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录