Phép nhân ma trận thưa thớt trong C ++

Giả sử chúng ta có hai ma trận A và B, chúng ta phải tìm kết quả của AB. Chúng tôi có thể giả định rằng số cột của A bằng số hàng của B.

Vì vậy, nếu đầu vào giống như [[1,0,0], [- 1,0,3]] [[7,0,0], [0,0,0], [0,0,1]] ,

thì đầu ra sẽ là [[7,0,0], [- 7,0,3]]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• r1:=kích thước của A, r2:=kích thước của B

• c1:=size of A [0], c2:=size of B [0]

• Xác định một ret của mảng 2D theo thứ tự r1 x c2

• Xác định một mảng thưa thớtA [r1] gồm các cặp

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • nếu A [i, j] không bằng 0 thì -

      • chèn {j, A [i, j]} vào cuối dòng chữ A [i]

• để khởi tạo i:=0, khi i

  • để khởi tạo j:=0, khi j

    • để khởi tạo k:=0, khi k

      • x:=phần tử đầu tiên của SliceA [i, j]

      • nếu B [x, k] không bằng 0 thì -

        • ret [i, k]:=ret [i, k] + phần tử thứ hai của thưaA [i, j] * B [x, k]

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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;
   }
};

Đầu vào

{{1,0,0},{-1,0,3}},{{7,0,0},{0,0,0},{0,0,1}}

Đầu ra

[[7, 0, 0, ],[-7, 0, 3, ],]