Leetcode 311. Sparse Matrix Multiplication (python)

题目

解法：暴力

这边主要讲一下怎么做矩阵乘法。假设我们有矩阵A，B，结果是C，那么

C[i][k] += A[i][j]*B[j][k]

从矩阵乘法的维度变化来考虑就可以理解了。
遍历的顺序不重要，下面几种都是ok的

class Solution:def multiply(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:ans = [[0]*len(B[0]) for _ in range(len(A))]# for i in range(len(A)):# for j in range(len(A[0])):# for b_j in range(len(B[0])):# ans[i][b_j] += A[i][j]*B[j][b_j]for i in range(len(A)):for b_i in range(len(B)):for b_j in range(len(B[0])):ans[i][b_j] += A[i][b_i]*B[b_i][b_j]return ans

解法2：

利用hashmap来储存非0元素。这应该是面试中比较标准的解法。一个encode来把sparse_matrx转换成dense_matrix。然后对dense_matrix做乘法，最后用decode把dense_matrix的结果转换为sparse_matrix的结果

implementation很直观的

class Solution:def multiply(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:def encode(sparse_matrix):dense_matrix = {
    }for i in range(len(sparse_matrix)):for j in range(len(sparse_matrix[0])):if sparse_matrix[i][j]:dense_matrix[(i,j)] = sparse_matrix[i][j]return dense_matrixdef decode(dense_matrix,row,col):sparse_matrix = [[0]*col for _ in range(row)]for (i,j),val in dense_matrix.items():sparse_matrix[i][j] = valreturn sparse_matrixA_dense = encode(A)B_dense = encode(B)ans_dense = collections.defaultdict(int)for (i,j) in A_dense.keys():for k in range(len(B[0])):if (j,k) in B_dense:ans_dense[(i,k)] += A_dense[(i,j)]*B_dense[(j,k)]return decode(ans_dense,len(A),len(B[0]))

二刷

用c++来写，由于pair或者vector不能作为key，所以转换一下。而且同时最后的结果直接生成就好，无需decode

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>using namespace std;
unordered_map<int,int> encode(vector<vector<int>>& sparse_matrix){
    unordered_map<int,int> dense_matrix;for(int i=0;i<sparse_matrix.size();i++){
    for(int j=0;j<sparse_matrix[0].size();j++){
    if(sparse_matrix[i][j] == 0) continue;dense_matrix[i*sparse_matrix[0].size()+j] = sparse_matrix[i][j];}}return dense_matrix;
}
vector<vector<int>> multiply(vector<vector<int>>& A,vector<vector<int>>& B){
    unordered_map<int,int> dense_A = encode(A);unordered_map<int,int> dense_B = encode(B);vector<vector<int>> C(A.size(),vector<int>(B[0].size(),0));for(auto it : dense_A){
    int i = it.first / A[0].size();int j = it.first % A[0].size();for(int k = 0;k < B[0].size();k++){
    if(dense_B.count(j*B[0].size()+k)){
    C[i][k] += it.second * dense_B[j*B[0].size()+k];}}}return C;
}int main()
{
    vector<vector<int>> A{
    {
    1,0,0},{
    -1,0,3}};vector<vector<int>> B{
    {
    7,0,0},{
    0,0,0},{
    0,0,1}};vector<vector<int>> C = multiply(A,B);for(auto& vec : C){
    for(auto& num : vec){
    cout << num << endl;}}return 0;
}

暴力时间复杂度：O(mnq)
优化后时间复杂度：O(mn+nq+num_zero_A*q)