-
Notifications
You must be signed in to change notification settings - Fork 2
/
SparseMatrixMultiplication.java
71 lines (64 loc) · 1.52 KB
/
SparseMatrixMultiplication.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package Leetcode;
/**
* @author kalpak
*
* 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:
*
* Input:
*
* A = [
* [ 1, 0, 0],
* [-1, 0, 3]
* ]
*
* B = [
* [ 7, 0, 0 ],
* [ 0, 0, 0 ],
* [ 0, 0, 1 ]
* ]
*
* Output:
*
* | 1 0 0 | | 7 0 0 | | 7 0 0 |
* AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
* | 0 0 1 |
*
*
* Constraints:
*
* 1 <= A.length, B.length <= 100
* 1 <= A[i].length, B[i].length <= 100
* -100 <= A[i][j], B[i][j] <= 100
*
*/
public class SparseMatrixMultiplication {
public static int[][] multiplyOptimized(int[][] A, int[][] B) {
int[][] result = new int[A.length][B[0].length];
for(int i = 0; i < A.length; i++) {
for(int k = 0; k < A[0].length; k++) {
if(A[i][k] != 0) {
for(int j = 0; j < B[0].length; j++) {
if(B[k][j] != 0)
result[i][j] += A[i][k] * B[k][j];
}
}
}
}
return result;
}
public int[][] multiplyNaive(int[][] A, int[][] B) {
int[][] result = new int[A.length][B[0].length];
for(int i = 0; i < A.length; i++) {
for(int j = 0; j < B[0].length; j++) {
for(int k = 0; k < A[0].length; k++) {
result[i][j] += A[i][k] * B[k][j];
}
}
}
return result;
}
}