How to Multiply Two Matrices in C++?
- 时间:2020-09-23 15:11:59
- 分类:网络文摘
- 阅读:154 次
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:
Input:
1 2 3 4 A = [ [ 1, 0, 0], [-1, 0, 3] ]A = [ [ 1, 0, 0], [-1, 0, 3] ]
1 2 3 4 5 B = [ [ 7, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ]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 |
The Matrix Multiplication Algorithm in C++
Given two matrices, if either one of them is empty, the multiplication result should be empty as well. The result matrix dimension is the [rowA, colB] and each element in the matrix should be the sum of the dot products for each row in A and each column in B i.e. r[i][j] = sum(A[i][k] * B[k][j]) where k is within [0, colA).
The straightforward/naive implementation of two matrix muplication using std::vector is as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution { public: vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) { vector<vector<int>> r; int rowA = A.size(); if (rowA == 0) return r; int colA = A[0].size(); if (colA == 0) return r; int rowB = B.size(); if (rowB == 0) return r; int colB = B[0].size(); if (colB == 0) return r; r.resize(rowA); for (int i = 0; i < rowA; ++ i) { r[i].resize(colB); } for (int i = 0; i < rowA; ++ i) { for (int j = 0; j < colB; ++ j) { for (int k = 0; k < colA; ++ k) { r[i][j] += A[i][k] * B[k][j]; } } } return r; } }; |
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> r;
int rowA = A.size();
if (rowA == 0) return r;
int colA = A[0].size();
if (colA == 0) return r;
int rowB = B.size();
if (rowB == 0) return r;
int colB = B[0].size();
if (colB == 0) return r;
r.resize(rowA);
for (int i = 0; i < rowA; ++ i) {
r[i].resize(colB);
}
for (int i = 0; i < rowA; ++ i) {
for (int j = 0; j < colB; ++ j) {
for (int k = 0; k < colA; ++ k) {
r[i][j] += A[i][k] * B[k][j];
}
}
}
return r;
}
};The time complexity is O(rowA * colB * colA).
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:Algorithm to Check if A String Matches a Pattern How to Get Free HTTPS Certificates via acme.sh? Algorithm to Replace All ?’s to Avoid Consecutive Repeatin How Does C++ STL min_element, max_element, minmax_element work f Using the External Fan to Cool the Hot AMD Radeon HD 6700 Graphi Algorithms to Compute the Dot Product of Two Sparse Vectors Algorithms to Compute the Largest Time for Given Digits How to Use Hash Map to Count the Frequencies of Values and Itera Ordered Three 2TB WD HDD to prolong the life expectancy of HPZ80 HPZ800 Server Does Not Support Hard Drives Larger Than 2TB
- 评论列表
-
- 添加评论