Java Simple Solution, HashMap


  • 0
    S

    I added the class cell which makes it easier to understand.
    We can use 2 Hash maps(one for each matrix) to make it more efficient.

    
    public class Solution {
        class Cell {
            int i;
            int j;
            Integer val;
            Cell(int i, int j, Integer val) {
                this.i = i;
                this.j = j;
                this.val = val;
            }
        }
        
        public int[][] multiply(int[][] A, int[][] B) {
            if(A == null || B == null || A[0] == null || B[0] == null) {
                return null;
            }
            Map<Integer, List<Cell>> map = new HashMap<>();
            int[][] result = new int[A.length][B[0].length];
            for(int i = 0; i < A.length; i++) {
                Integer curInteger = new Integer(i);
                for(int j = 0; j < A[0].length; j++) {
                    if(A[i][j] != 0) {
                        if(map.containsKey(curInteger)) {
                            map.get(i).add(new Cell(i, j, A[i][j]));
                        }
                        else {
                            List<Cell> list = new ArrayList<>();
                            list.add(new Cell(i, j, A[i][j]));
                            map.put(curInteger, list);
                        }
                    }
                }
            }
            
            for(Integer key:map.keySet()) {
                List<Cell> list = map.get(key);
                //list = [(1,1,4), (1,4,7)]
                for(int j = 0; j < B[0].length; j++) {
                     for(Cell cur:list) {
                         result[key][j]+=cur.val*B[cur.j][j];
                     }
                }
            }
            
            
            return result;
        }
    }

Log in to reply
 

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