龙空技术网

大厂面试真题详解:稀疏矩阵乘法

阿里云开发者 150

前言:

今天小伙伴们对“多矩阵乘法优化算法”大约比较注重,你们都需要剖析一些“多矩阵乘法优化算法”的相关内容。那么小编也在网络上网罗了一些关于“多矩阵乘法优化算法””的相关内容,希望同学们能喜欢,看官们一起来学习一下吧!

简介: 大厂面试真题详解:稀疏矩阵乘法

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

原文:

标签: #多矩阵乘法优化算法