[LeetCode] 311. Sparse Matrix Multiplication 稀疏矩阵相乘
Given two sparse matrices A and B, return the result of AB.
You may assume that A's column number is equal to B's row number.
Example:
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 |
这道题让我们实现稀疏矩阵相乘,稀疏矩阵的特点是矩阵中绝大多数的元素为0,而相乘的结果是还应该是稀疏矩阵,即还是大多数元素为0,那么使用传统的矩阵相乘的算法肯定会处理大量的0乘0的无用功,所以需要适当的优化算法,使其可以顺利通过 OJ,由于一个 i x k 的矩阵A乘以一个 k x j 的矩阵B会得到一个 i x j 大小的矩阵C,来看结果矩阵中的某个元素C[i][j]是怎么来的,起始是 A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][k]*B[k][j],那么为了不重复计算0乘0,首先遍历A数组,要确保 A[i][k] 不为0,才继续计算,然后遍历B矩阵的第k行,如果 B[K][J] 不为0,累加结果矩阵 res[i][j] += A[i][k] * B[k][j],这样就能高效的算出稀疏矩阵的乘法,参见代码如下:
解法一:
class Solution { public: vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) { vector<vector<int>> res(A.size(), vector<int>(B[0].size())); for (int i = 0; i < A.size(); ++i) { for (int k = 0; k < A[0].size(); ++k) { if (A[i][k] != 0) { for (int j = 0; j < B[0].size(); ++j) { if (B[k][j] != 0) res[i][j] += A[i][k] * B[k][j]; } } } } return res; } };
再来看另一种方法,这种方法其实核心思想跟上面那种方法相同,稍有不同的是用一个二维矩阵矩阵来记录每一行中,各个位置中不为0的列数和其对应的值,然后遍历这个二维矩阵,取出每行中不为零的列数和值,然后遍历B中对应行进行累加相乘,参见代码如下:
解法二:
class Solution { public: vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) { vector<vector<int>> res(A.size(), vector<int>(B[0].size())); vector<vector<pair<int, int>>> v(A.size(), vector<pair<int,int>>()); for (int i = 0; i < A.size(); ++i) { for (int k = 0; k < A[i].size(); ++k) { if (A[i][k] != 0) v[i].push_back({k, A[i][k]}); } } for (int i = 0; i < A.size(); ++i) { for (int k = 0; k < v[i].size(); ++k) { int col = v[i][k].first; int val = v[i][k].second; for (int j = 0; j < B[0].size(); ++j) { res[i][j] += val * B[col][j]; } } } return res; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/311
类似题目:
Dot Product of Two Sparse Vectors
参考资料:
https://leetcode.com/problems/sparse-matrix-multiplication/
https://leetcode.com/discuss/77235/ac-soluiton-code
https://leetcode.com/discuss/71912/easiest-java-solution
相关文章
- Java实现 LeetCode 838 推多米诺(暴力模拟)
- Java实现 LeetCode 766 托普利茨矩阵(暴力)
- Java实现 LeetCode 764 最大加号标志(暴力递推)
- Java实现 LeetCode 391 完美矩形
- Java实现 LeetCode 378 有序矩阵中第K小的元素
- Java实现 LeetCode 373 查找和最小的K对数字
- Java实现 LeetCode 344 反转字符串
- Java实现 LeetCode 329 矩阵中的最长递增路径
- Java实现 LeetCode 304 二维区域和检索 - 矩阵不可变
- Java实现 LeetCode 160 相交链表
- Java实现 LeetCode 106 从中序与后序遍历序列构造二叉树
- Java实现 LeetCode 74 搜索二维矩阵
- Java实现 LeetCode 73 矩阵置零
- Java实现 LeetCode 73 矩阵置零
- Java实现 LeetCode 59 螺旋矩阵 II
- Java实现 LeetCode 137 只出现一次的数字
- Java实现 LeetCode 240 搜索二维矩阵 II
- LeetCode: 221_Maximal Square | 二维0-1矩阵中计算包含1的最大正方形的面积 | Medium
- LeetCode(74):搜索二维矩阵
- LeetCode(73):矩阵置零
- 【LeetCode 中等 矩阵】面试题 01.07. 旋转矩阵
- 【LeetCode Python实现】22. 括号生成(中等)
- Leetcode 1572. 矩阵对角线元素的和
- Leetcode 566. 重塑矩阵
- Leetcode 1992. 找到所有的农场组(可以,一次过)
- Leetcode 73. 矩阵置零
- [LeetCode] 29. Divide Two Integers(不使用乘除取模,求两数相除) ☆☆☆
- leetcode 1351. 统计有序矩阵中的负数 js实现
- 【LeetCode从零单排】No 3 Longest Substring Without Repeating Characters
- leetcode——Search a 2D Matrix 二维有序数组查找(AC)
- 【Leetcode刷题Python】51. N 皇后