How to Multiply Two Matrices in C++?
- 时间:2020-09-23 15:11:59
- 分类:网络文摘
- 阅读:88 次
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) —
推荐阅读:Depth First Search Algoritm to Compute The k-th Lexicographical Blogging From Your Tablet – The Ins and Outs Saudi Blogger’s Wife Looks to West for Help Singaporean Amos Yee Fights for Free Speech Gay Catholic Blogger to Visit White House 5 Tools for Making Your Content Visual Top Website Builders for SEO Is Blogging Taking a Toll on Your Eyes? Top New Media Tips for Entrepreneurs Is Your Blog A Bore? – 5 Ways to Make Your Blog More Visually In
- 评论列表
-
- 添加评论