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 2 3 | 1 0 0 | | 7 0 0 | | 7 0 0 | AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 | | 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 |
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). See also: Teaching Kids Programming – Matrix Add, Subtraction and Multiplication Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Compute the Number of Equivalent Domino Pairs?
Next Post: How to Count the Path Sum from a Binary Tree using Depth First Search Algorithm?