文章目录
1. 题目2. 解题2.1 暴力求解2.2 选取都不为0的行和列相乘
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
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
