大廠面試真題詳解：稀疏矩陣乘法

給定兩個 稀疏矩陣 A 和 B，傳回AB的結果。

您可以假設A的列數等于B的行數。

線上評測位址：

領扣題庫官網 樣例1

Input: 
[[1,0,0],[-1,0,3]]
[[7,0,0],[0,0,0],[0,0,1]]
Output:
[[7,0,0],[-7,0,3]]
Explanation:
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 |           

樣例2

Input:
[[1,0],[0,1]]
[[0,1],[1,0]]
Output:
[[0,1],[1,0]]           

算法：模拟

思路

矩陣乘法的實作：一個m行n列的矩陣A，與一個n行p列的矩陣B可以相乘，得到的結果AB是一個m行p列的矩陣，其中的第i行第j列位置上的數AB(i,j)為，矩陣A第i行上的n個數與矩陣B第j列上的n個數一一對應相乘後，所得到的n個乘積之和。直接模拟即可。

複雜度分析

空間複雜度O(n^2)

時間複雜度O(n^3)

public class Solution {
    /**
     * @param A: a sparse matrix
     * @param B: a sparse matrix
     * @return: the result of A * B
     */
    public int[][] multiply(int[][] A, int[][] B) {
        int rowA = A.length, columnA = A[0].length;
        int rowB = B.length, columnB = B[0].length;
        // AB為 rowA * columnB 大小的矩陣
        int[][] AB = new int [rowA][columnB];
        for (int i = 0; i < rowA; i++){
            for (int j = 0; j < columnB; j++){
                // 求出每一項
                int sum = 0;
                for (int k = 0; k < columnA; k++){
                    sum += A[i][k] * B[k][j];
                }
                AB[i][j] = sum;
            }
        }
        return AB;
    }
}           

更多題解參考：

九章官網solution