之前听说 FB 考过 2 道 hard 题，还只给 40 分钟的……

FB 有时候就是逼你背答案，现在想想也有道理，愿意刷题也能看出工作态度，不过国内大厂应该很难“仅”靠刷题上岸吧？

给定两个 稀疏矩阵 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;     } }  

大佬有話說 (0)