How to Multiply Two Matrices in C++?
- 时间:2020-09-23 15:11:59
- 分类:网络文摘
- 阅读:98 次
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) —
推荐阅读:The Contiguous Binary Array with Equal Numbers of Ones and Zeros Microbit Programming: Showing a Running Pixel on the LED How to Print Immutable Linked List in Reverse using Recursion or The Most Useful Tools for Reverse Phone Lookup How to Solve the WIFI (Wireless Networks) Intermittency Issues? How to Reverse a Linked List in Javascript? Bash Function to Check if a Kubernetes Pod Name is Valid VBScript Function to Convert an Integer to Binary String Represe Find Maximum Connected Colors (Values) in a 2D Grid using DFS or Algorithms to Shift a 2D Grid/Matrix In-Place
- 评论列表
-
- 添加评论