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 
评论列表
添加评论