Can anyone help me to improve my program(138 ms)?


  • 0
    C
    public int[][] multiply(int[][] A, int[][] B) {
        Map<Integer, Map<Integer,Integer>> map=new HashMap<>();
        int b=A.length;
        int a=A[0].length;
        int c=B[0].length;
        int result[][]=new int[b][c];
        for(int i=0;i<b;i++){
            Map<Integer,Integer> mapp=new HashMap<>();
            map.put(i,mapp);
            for(int j=0;j<a;j++){
                if(A[i][j]!=0) {map.get(i).put(j,A[i][j]);}
            }
            if(map.get(i).isEmpty()) map.remove(i);           
        }
        for(int i=0;i<c;i++){
            for(int j:map.keySet()){
                for(int k:map.get(j).keySet()){
                    if(B[k][i]!=0) result[j][i]+=B[k][i]*map.get(j).get(k);
                }
            }
        }
           
        return result;
    }
    

    I understand this is not the best way to solve the problem. Could anyone try improve it to run faster?


  • 0
    T

    You do not need a Map for that. Here is my simple solution in C++:

    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int aR = A.size();
        int aC = A[0].size();
    
        int bR =  B.size();
        int bC = B[0].size();
        
        vector<bool> Ab(aR,false);
        
        vector<bool> Bb(bC,false);
        
        for (int i = 0; i <aR; i++)
        {
            int j = 0;
            for (; j<aC; j++)
                if (A[i][j])
                {
                    Ab[i] = true;
                    break;
                }
        }
    
    
        for (int i = 0; i <bC; i++)
        {
            int j = 0;
            for (; j<bR; j++)
                if (B[j][i])
                {
                    Bb[i] = true;
                    break;
                }
        }
        
        
        vector<vector<int>> res(aR, vector<int>(bC,0));
        
        for (int i = 0; i <aR; i++)
        {
            if (!Ab[i]) continue;
            for (int j = 0; j <bC; j++)
            {
                if (!Bb[j]) continue;
                for (int p = 0; p<bR; p++)
                    res[i][j]+=A[i][p]*B[p][j];
            }
        }    
        return res;
    }

Log in to reply
 

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