Matrix Multiplication
We learn matrix multiplication in school, but it is much simpler with the help of programming.
Basically two matrices A[n][k] and B[k][m] can be multiplied in time O(n*k*m). Exemplified by this LC problem: https://leetcode.com/problems/sparse-matrix-multiplication/
The solution is given down below, literally just following the rules of matrices multiplication. Cheers, ACC.
public class Solution
{
public int[][] Multiply(int[][] A, int[][] B)
{
int[][] result = new int[A.Length][];
for (int i = 0; i < result.Length; i++)
{
result[i] = new int[B[0].Length];
}
for (int r = 0; r < result.Length; r++)
{
for (int c = 0; c < result[0].Length; c++)
{
result[r][c] = 0;
for (int i = 0; i < A[0].Length; i++)
{
result[r][c] += (A[r][i] * B[i][c]);
}
}
}
return result;
}
}
Basically two matrices A[n][k] and B[k][m] can be multiplied in time O(n*k*m). Exemplified by this LC problem: https://leetcode.com/problems/sparse-matrix-multiplication/
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 |
The solution is given down below, literally just following the rules of matrices multiplication. Cheers, ACC.
public class Solution
{
public int[][] Multiply(int[][] A, int[][] B)
{
int[][] result = new int[A.Length][];
for (int i = 0; i < result.Length; i++)
{
result[i] = new int[B[0].Length];
}
for (int r = 0; r < result.Length; r++)
{
for (int c = 0; c < result[0].Length; c++)
{
result[r][c] = 0;
for (int i = 0; i < A[0].Length; i++)
{
result[r][c] += (A[r][i] * B[i][c]);
}
}
}
return result;
}
}
Comments
Post a Comment