My Java solution based on triple.


  • 2
    A

    public class Solution {

    class Point{ // A linked list storing the (row_no, col_no, value) of every existing values.
    	private int row;
    	private int col;
    	private int val;
    	Point next;
    	Point(int row,int col,int value){
    		this.row = row;
    		this.col = col;
    		this.val = value;
    		this.next = null;
    	}
    }
    
    public int[][] multiply(int[][] A, int[][] B) {
        
    	Point C = createTuple(A);
    	Point D = createTuple(B);
    	Point DH = D;
    	int[][] result = new int[A.length][B[0].length];
    	while(C!=null){
    		while(D!=null){
    			if(D.row==C.col){ //For two points m(i,j) , n(k,l), excute m*n only if (j==k) and add the result into another matrix on the position of (i,l);
    				result[C.row][D.col] += C.val * D.val; 
    			}
    			D = D.next;
    		}
    		C = C.next;
    		D = DH;
    	}
    	
    	return result;
    	
    }
    
    private Point createTuple(int[][] A){ // Convert the sparse matrix into 3-tuple.
    	Point head = null;
    	Point next = null;
    	int rown = A.length;
    	int coln = A[0].length;
    	for(int i = 0;i<rown;i++){
    		for(int j = 0;j<coln;j++){
    			if(A[i][j]!=0){
    				Point cur = new Point(i,j,A[i][j]);
    				if(head==null){
    					head = cur;
    					next = head;
    				}else{
    					next.next=cur;
    					next = next.next;
    				}
    			}
    		}
    	}
    	return head;
    }
    

    }


  • 0
    Q

    really clear solution!


Log in to reply
 

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