大厂面试真题详解:稀疏矩阵乘法-阿里云开发者社区

开发者社区> 算法编程> 正文

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

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

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接