두 개의 행렬 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 차수의 2D 배열 ret를 정의합니다.
-
쌍의 sparseA[r1] 배열 정의
-
initialize i :=0의 경우, i
-
j 초기화의 경우 :=0, j
-
A[i, j]가 0과 같지 않으면 -
-
{ j, A[i, j] } sparseA[i]
끝에 삽입
-
-
-
-
initialize i :=0의 경우, i
-
initialize j :=0인 경우 j
-
초기화 k :=0의 경우 k
-
x :=sparseA[i, j]의 첫 번째 요소
-
B[x, k]가 0이 아닌 경우 -
-
ret[i, k] :=ret[i, k] + sparseA[i, j]의 두 번째 요소 * B[x, k]
-
-
-
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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, ],]