golang 解法, 执行用时: 4 ms, 内存消耗: 3.1 MB, 提交时间: 2023-10-17 11:51:10

// 直接计算
func multiply(mat1 [][]int, mat2 [][]int) [][]int {
    m,n,l := len(mat1),len(mat2[0]),len(mat1[0])
    ans := make([][]int, m)
    for i:=0;i<m;i++{
        ans[i] = make([]int, n)
    }
    // 三层循环进行计算
    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            for k:=0;k<l;k++{
                ans[i][j] += mat1[i][k]*mat2[k][j]
            }
        }
    }
    return ans  
}

// 运用稀疏性质
func multiply2(mat1 [][]int, mat2 [][]int) [][]int {
    m,n,l := len(mat1), len(mat2[0]), len(mat1[0])
    ans := make([][]int, m)
    
    for i:=0;i<m;i++{
        ans[i] = make([]int, n)
    }

    for i:=0; i<m; i++{
        for k:=0;k<l;k++{
            // mat1[i][k]若为0， mat1[i][k]*mat2[k][j]也为0，故可以跳过，减少循环次数
            if mat1[i][k] == 0{
                continue
            }
            for j:=0;j<n;j++{
                ans[i][j] += mat1[i][k]*mat2[k][j]
            }
        } 
    }
    return ans
}

// 先处理再计算
func multiply3(mat1 [][]int, mat2 [][]int) [][]int {
    m,n:= len(mat1),len(mat2[0])
    ans := make([][]int,m)
    for i:=0; i<m;i++{
        ans[i] = make([]int, n)
    }

    noneZeroA := getNoneZeroMat(mat1)
    noneZeroB := getNoneZeroMat(mat2)

    for _, m1 := range noneZeroA{
        // 每个m1包含的数据：i,j,matrix[i][j]
        for _, m2 := range noneZeroB{
            // 这里这么判断的原因：mat1和mat2相乘，
            // 只有mat1的数据的列数和mat2的行数相等才会进行计算
            if m1[1]==m2[0]{
                ans[m1[0]][m2[1]] += m1[2]*m2[2]
            }
        }
    }
    return ans
}

func getNoneZeroMat(matrix [][]int) [][]int{
    m, n := len(matrix),len(matrix[0])
    ans := [][]int{}

    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if matrix[i][j]!=0{
                ans = append(ans, []int{i,j,matrix[i][j]})
            }
        }
    }

    return ans
}

java 解法, 执行用时: 2 ms, 内存消耗: 42.4 MB, 提交时间: 2023-10-17 11:48:17

class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        Map<Integer, Map<Integer, Integer>> map1 = new HashMap<>();
        Map<Integer, Map<Integer, Integer>> map2 = new HashMap<>();
        //构造矩阵1的哈希表        
        //矩阵1的哈希表格式Map<行标, Map<列标，值>>
        for(int i = 0; i < mat1.length; i++){
            map1.put(i, new HashMap<>());
            for(int j = 0; j < mat1[i].length; j++){
                if(mat1[i][j] != 0){
                    map1.get(i).put(j, mat1[i][j]);
                }
            }
        }
        //构造矩阵2的哈希表        
        //矩阵2的哈希表格式Map<列标, Map<行标，值>> 
        for(int i = 0; i < mat2.length; i++){
            for(int j = 0; j < mat2[i].length; j++){
                if(mat2[i][j] != 0){
                    if(!map2.containsKey(j))
                        map2.put(j, new HashMap<>());
                    map2.get(j).put(i, mat2[i][j]);
                }
            }
        }

        int[][] res = new int[mat1.length][mat2[0].length];
        for(int i = 0; i < mat1.length; i++){
            for(int j = 0; j < mat2[0].length; j++){
                Map<Integer, Integer> row = map1.get(i);
                Map<Integer, Integer> col = map2.get(j);
                for(int rowIndex : row.keySet()){
                    if(col != null && col.containsKey(rowIndex))
                        res[i][j] += row.get(rowIndex) * col.get(rowIndex);
                }
            }
        }
        return res;
    }
}

cpp 解法, 执行用时: 16 ms, 内存消耗: 8.3 MB, 提交时间: 2023-10-17 11:47:42

class Solution {
public:
    // 直接模拟
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> res(A.size(),vector<int>(B[0].size()));//定义需要的特定大小的矩阵
        //实现矩阵的乘法
        for(int i=0;i<A.size();++i){
            for(int j=0;j<B[0].size();++j){
                for(int k=0;k<A[0].size();++k){
                    res[i][j]+=A[i][k]*B[k][j];
                }
            }
        }
        return res;
    }
    
    // 先统计非零，再计算
    vector<vector<int>> multiply2(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> res(A.size(),vector<int>(B[0].size()));
        //统计数组A中的非零元素
        vector<vector<int>> A_tmp(A.size());
        for(int i=0;i<A.size();++i){
            for(int j=0;j<A[0].size();++j){
                if(A[i][j]){
                    A_tmp[i].push_back(j);
                }
            }
        }
        //统计数组B中的非零元素
        vector<vector<int>> B_tmp(B[0].size());
        for(int i=0;i<B[0].size();++i){
            for(int j=0;j<B.size();++j){
                if(B[j][i]){
                    B_tmp[i].push_back(j);
                }
            }
        }
		//处理矩阵的乘法
        for(int i=0;i<A.size();++i){
            for(int j=0;j<B[0].size();++j){
            	//使用非零元素较少的数组来实现乘法
                if(A_tmp[i].size()<B_tmp[j].size()){
                    for(int&k:A_tmp[i]){
                        res[i][j]+=A[i][k]*B[k][j];
                    }
                }
                else{
                    for(int&k:B_tmp[j]){
                        res[i][j]+=A[i][k]*B[k][j];
                    }
                }
            }
        }
        //返回结果
        return res;
    }
};

python3 解法, 执行用时: 44 ms, 内存消耗: 16.5 MB, 提交时间: 2023-10-17 11:46:14

class Solution:
    # 先生成稀疏的三元组表示，再逐对运算
    def multiply(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        m = len(A)
        n = len(B[0])
        posA = self.getSparseRepresentation(A)
        posB = self.getSparseRepresentation(B)
        res = [[0 for i in range(n)] for j in range(m)]
        for valA, xA, yA in posA:
            for valB, xB, yB in posB:
                if yA == xB:
                    res[xA][yB] += valA * valB
        return res
    
    def getSparseRepresentation(self, A: List[List[int]]):
        posList = []
        m = len(A)
        n = len(A[0])
        for i in range(m):
            for j in range(n):
                if A[i][j] != 0:
                    posList.append([A[i][j],i,j])
        return posList