311 Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]


     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

分析

输入：两个二维数组int[ ][ ] A, B 输出：一个二维数组int[ ][ ] C

感觉就是考察数组运算

1.既然是数组，就需要初始化确定size A[x][y] * B[y][z] = C[x][z]

思路1

1.求输入数组的size

1）java有现成函数么？

对于方形的二维array，可以利用length来分别求行数，与列数

int row = a.length;
int col = a[0].length;

2.求输出数组的size

3.利用循环来进行数组运算

1)两个for循环，一个对C的row循环，一个对C的col循环，因此可以得到C的每一个元素

2）在求每一个元素的值时候又需要有一个循环分别遍历A的col与B的row

for(int row_c=0; row_c<row_a; row_c++) {
    for(int col_c=0; col_c<col_b; col_c++) {
        //C[row_c][col_c] = A[row_c][0]*B[0][col_c] + A[row_c][1]*B[1][col_c] + ... + A[row_c][col_a]*B[row_b][col_c]
        for(int i=0; i<col_a; i++ ) {
            C[row_c][col_c] += A[row_c][i]*B[i][col_c];
        }
    }
}

思路1遇到的问题：Time Limit Exceed

思路2

如何减少计算的复杂度？？？

难道关键词是：sparse！！！？？？

由于有A与B矩阵的多处是0，因此可以判断是否为0，只有不为0时才运行乘法操作

for(int i=0; i<col_a; i++ ) {
    if(A[row_c][i] != 0 && B[i][col_c] != 0)
    C[row_c][col_c] += A[row_c][i]*B[i][col_c];
}

思路2结果：确实accept了，但是运算时间还是略长。

思路3：有更快的方法么？

tag提示：hash table。。。。。日了狗了。。。

1.hash table 的特点：根据key可以在O(1)内找到value

那么在这道题中有什么需要快速查找的呢？-》A不全为0的行

把A中不全为0的行存起来,然后遍历这个hashtable与对应的B的列相乘

思路3实现中遇到的问题：

1.Hashtable的操作

Hashtable<K, V> ht = new Hashtable<K, V>();
ht.put(K, V);
Set<Map.Entry<K, V>> s = ht.entrySet();

2.Set的操作

Iterator<E> iter = s.iterator();

3.Iterator的操作

iter.hasNext();
iter.next();

需要特别注意的是：.next()取出的对象要用ref指引，因为每次next后iterator的index就会移动。

iter.next().getKey();
iter.next().getValue();//得出的value不是之前对应key的！

Map.Entry<K,V> entry = iter.next();//create ref
entry.getKey();
entry.getValue();//此处的value才对应key

4.Map.Entry的操作

entry.getKey();
entry.getValue();

AC code

import java.util.*;
public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {

    //input array  size
    int row_a = A.length;
    int col_a = A[0].length;
    int row_b = B.length;
    int col_b = B[0].length;
    //output array size
    int[][] C = new int[row_a][col_b];    

    Hashtable<Integer, int[]> A_ht = new Hashtable<Integer, int[]>();
    for(int i=0; i<row_a; i++) {
        for(int j=0; j<col_a; j++) {
            if(A[i][j] != 0) {
                A_ht.put(i, A[i]);
                break;
            }
        }
    }

    Set<Map.Entry<Integer, int[]>> non0ArowSet = A_ht.entrySet();
    Iterator<Map.Entry<Integer, int[]>> iter = non0ArowSet.iterator();
    while(iter.hasNext()) {
        Map.Entry<Integer, int[]> e = iter.next();
        int non0Arow = e.getKey();
        int[] non0ArowArray = e.getValue();
        System.out.println(non0Arow);
        System.out.println(Arrays.toString(non0ArowArray));
        for(int i=0; i<col_b; i++) {
            for(int j=0; j<row_b; j++) {
                if(A[non0Arow][j] !=0 && B[j][i] !=0) {
                C[non0Arow][i] += A[non0Arow][j]*B[j][i];
                }
            }
        }
    }
    return C;
    }

}