C++_2 Solutions (Map or No map)_Accepted


  • -1

    No map: 26ms, 65.90%
    Because res[iA][jB] = sum of (matrix A[iA][jA] * matrix B[jA][jB]), so if matrix A[iA][jA] == 0 or matrix B[jA][jB] == 0, we can skip that loop.

    class Solution {
    public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> res(A.size(), vector<int>(B[0].size(), 0));
        
        for(int iA = 0; iA < A.size(); ++iA){
            for(int jA = 0; jA < A[0].size(); ++jA){
                if(A[iA][jA] != 0){
                    for(int jB = 0; jB < B[0].size(); ++jB){
                        if(B[jA][jB] != 0){res[iA][jB] += A[iA][jA]*B[jA][jB];}
                    }
                }
            }
        }
        return res;
    }
    };
    

    0_1476823461922_D02B80CE-EFA4-4664-A805-C677C057BD4C.png

    Using map: 26ms, 65.90%, actually I just used the vector instead of map.
    The main idea is that we use a vector check (whose rows are size A.size()) to store the non-zero information in matrix A. if A[i][j] is not equal to zero, then the index j will be used to find corresponding B[j][jB] in matrix B. So we store a pair<int, int>(j, A[i][j]), and then we can use loop to find out our result matrix.

    class Solution {
    public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> res(A.size(), vector<int>(B[0].size(), 0));
        vector<vector<pair<int, int>>> check(A.size());
        
        for(int i = 0; i < A.size(); ++i){
            for(int j = 0; j < A[0].size(); ++j){
                if(A[i][j]){check[i].push_back(std::make_pair(j,A[i][j]));}
            }
        }
        
        for(int iA = 0; iA < A.size(); ++iA){
            for(int k = 0; k < check[iA].size(); ++k){
                int jA = check[iA][k].first;
                int valA = check[iA][k].second;
                for(int jB = 0; jB < B[0].size(); ++jB){
                    if(B[jA][jB]) res[iA][jB] += valA * B[jA][jB];
                }
            }
        }
        return res;
    }
    };
    

    0_1476826088648_666F62C8-F829-4D6B-995F-4B242FA1BA3D.png


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.