資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++稀疏矩陣乘法
假設我們有兩個矩陣 A 和 B，我們需要找到 AB 的結果。我們可以假設 A 的列數等於 B 的行數。
所以，如果輸入類似於 [[1,0,0],[-1,0,3]] [[7,0,0],[0,0,0],[0,0,1]]，
| 1 | 0 | 0 |
| -1 | 0 | 3 |
| 7 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 1 |
那麼輸出將是 [[7,0,0],[-7,0,3]]
| 7 | 0 | 0 |
| -7 | 0 | 3 |
為了解決這個問題，我們將遵循以下步驟：
r1 := A 的大小，r2 := B 的大小
c1 := A[0] 的大小，c2 := B[0] 的大小
定義一個 r1 x c2 階的二維陣列 ret
定義一個包含 pair 的陣列 sparseA[r1]
初始化 i := 0，當 i < r1 時，更新（i 加 1），執行：
初始化 j := 0，當 j < c1 時，更新（j 加 1），執行：
如果 A[i, j] 不等於 0，則：
將 { j, A[i, j] } 插入 sparseA[i] 的末尾
初始化 i := 0，當 i < r1 時，更新（i 加 1），執行：
初始化 j := 0，當 j < sparseA[i] 的大小，更新（j 加 1），執行：
初始化 k := 0，當 k < c2 時，更新（k 加 1），執行：
x := sparseA[i, j] 的第一個元素
如果 B[x, k] 不等於 0，則：
ret[i, k] := ret[i, k] + sparseA[i, j] 的第二個元素 * B[x, k]
返回 ret
示例
讓我們來看下面的實現來更好地理解：
class Solution {
public:
vector<vector<int<> multiply(vector<vector<int<>& A, vector<vector<int<>& B) {
int r1 = A.size();
int r2 = B.size();
int c1 = A[0].size();
int c2 = B[0].size();
vector < vector <int< > ret(r1, vector <int< (c2));
vector < pair <int, int> > sparseA[r1];
for(int i = 0; i < r1; i++){
for(int j = 0; j < c1; j++){
if(A[i][j] != 0)sparseA[i].push_back({j, A[i][j]});
}
}
for(int i = 0; i < r1; i++){
for(int j = 0; j < sparseA[i].size(); j++){
for(int k = 0; k < c2; k++){
int x = sparseA[i][j].first;
if(B[x][k] != 0){
ret[i][k] += sparseA[i][j].second * B[x][k];
}
}
}
}
return ret;
}
};輸入
{{1,0,0},{-1,0,3}},{{7,0,0},{0,0,0},{0,0,1}}輸出
[[7, 0, 0, ],[-7, 0, 3, ],]
更新於：2020年11月18日
2K+ 次瀏覽
廣告