C++ AC Code 23ms How can improve my code? Need your suggestion~~


  • 0
    T

    Hello, here is my ac code using 23ms. I change the 2D matrix to 1D array and save the index as key and numbers as the value of hashmap.
    I wonder how people could get faster with unordered map or they have a better data structures or solutions. Thank you.

    class Solution {
    private:
        int A_length;
        int A_width;
        int B_length;
        int B_width;
    private:
        void preProcess(vector<vector<int>>& matrix, unordered_map<int, int>& store) {
            int index = 0;
            for (int i = 0; i < matrix.size(); i++) {
                for (int j = 0; j < matrix[0].size(); j++) {
                    if (matrix[i][j] == 0) {
                        index++;
                        continue;
                    }
                    else {
                        store[index] = matrix[i][j];
                     //   cout<<index<<": "<<matrix[i][j]<<endl;
                    }
                    index++;
                }
            }
        }
        vector<vector<int>> multiplyHelper(unordered_map<int, int>& A_store, unordered_map<int, int>& B_store) {
         //   unordered_map<int, int> result_store;
            vector<vector<int>> result(A_length, vector<int>(B_width, 0));
            unordered_map<int, int>::iterator it_a;
            unordered_map<int, int>::iterator it_b;
            for (it_a = A_store.begin(); it_a != A_store.end(); it_a++) {
                for (it_b = B_store.begin(); it_b != B_store.end(); it_b++) {
                    int num1_row = it_a->first / A_width;
                    int num1_col = it_a->first % A_width;
                    int num2_row = it_b->first / B_width;
                    int num2_col = it_b->first % B_width;
                 //   cout<<num1_row<<" "<<num1_col<<" "<<num2_row<<" "<<num2_col<<endl;
                    if (num1_col != num2_row)
                        continue;
                    else {
                        int digit = it_a->second * it_b->second;
                        result[num1_row][num2_col] += digit;
                    }
                }   
            }
            
            return result;
        }
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            A_length = A.size();
            A_width = A[0].size();
            B_length = B.size();
            B_width = B[0].size();
            unordered_map<int, int> A_store;
            unordered_map<int, int> B_store;
            //Preprocess
            preProcess(A, A_store);
            preProcess(B, B_store);
            return multiplyHelper(A_store, B_store);
        }
    };
    

Log in to reply
 

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