สมมติว่ามีเมทริกซ์สองอัน 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]
กำหนดอาร์เรย์ 2 มิติ ret ขนาด r1 x c2
กำหนดอาร์เรย์ sparseA[r1] ของ pairs
ลูป i := 0 ถึง r1-1 ทำ −
ลูป j := 0 ถึง c1-1 ทำ −
ถ้า A[i][j] ไม่เท่ากับ 0 แล้ว −
แทรก { j, A[i][j] } ที่ท้ายของ sparseA[i]
ลูป i := 0 ถึง r1-1 ทำ −
ลูป j := 0 ถึงขนาดของ sparseA[i]-1 ทำ −
ลูป k := 0 ถึง c2-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, ],]
