2017/3/26 16:09:31

问题：求解稀疏矩阵乘法

 

版本1：朴素算法  θ(n

³)     采用常规矩阵乘法公式   

public static int[][] SparseMatrixMultiplication( int[][] A , int[][] B ){	int M = A.length;	int N = B[0].length;//取列长	int K = A[0].length;	int[][] C = new int[M][N];	for ( int i=0; i

　　

版本2：分治法 θ(n

³)    利用分块矩阵乘法性质

public static void main(String[] args) {		int[][] A = { {1,2,3},{4,5,6}};		int[][] B = { {1,2},{3,4},{5,6}};		int[][] C = SparseMatrixMultiplication(A, B);		for ( int i=0;i

　　

版本3： 既然是稀疏矩阵，大部分元素是0，所以可以剪掉多余的乘法运算。A的某一行全为0或者B的某一列全为0都可以省略计算。

Python

class Solution(object):    def multiply(self, A, B):        if len(A)==0 or len(B)==0: return 0        m, n = len(A), len(B[0])        res = [ [0]*n for i in range(m) ]         zerom, zeron = [True]*m, [True]*n        for i in range(m):            for index in range(len(A[0])):                if A[i][index]!=0:                    zerom[i] = False                    break        for i in range(n):            for index in range(len(B)):                if B[index][i]!=0:                    zeron[i] = False                    break        for i in range(m):            if zerom[i]==True: continue            for j in range(n):                if zeron[j]==True: continue                for mul_ind in range(len(A[0])):                    res[i][j] += A[i][mul_ind] * B[mul_ind][j]        return res