LeetCode 311. 稀疏矩阵的乘法

1. 题目

给你两个 稀疏矩阵 A 和 B，请你返回 AB 的结果。
你可以默认 A 的列数等于 B 的行数。

请仔细阅读下面的示例。

示例：
输入：
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 |

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sparse-matrix-multiplication
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 暴力求解

• 3层 for 循环

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> ans(A.size(), vector<int>(B[0].size(), 0));
        int i, j, k, sum;
        for(i = 0; i < A.size(); ++i)
        	for(j = 0; j < B[0].size(); ++j)
        	{
        		sum = 0;
        		for(k = 0; k < A[0].size(); ++k)
        			sum += A[i][k]*B[k][j];
        		ans[i][j] = sum;
        	}
        return ans;
    }
};

24 ms 8.4 MB

2.2 选取都不为0的行和列相乘

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<bool> r_all0(A.size(),true);
        vector<bool> c_all0(B[0].size(),true);
        int i, j, k, sum;
        bool flag = false;
        for(i = 0; i < A.size(); ++i)
        {
            flag = false;
            for(j = 0; j < A[0].size(); ++j)
            {
                if(A[i][j])
                {
                    flag = true;
                    break;
                }
            }
            if(flag)
                r_all0[i] = false;
        }
        for(j = 0; j < B[0].size(); ++j)
        {
            flag = false;
            for(i = 0; i < B.size(); ++i)
            {
                if(B[i][j])
                {
                    flag = true;
                    break;
                }
            }
            if(flag)
                c_all0[j] = false;
        }
        vector<vector<int>> ans(A.size(), vector<int>(B[0].size(), 0));
        for(i = 0; i < A.size(); ++i)
        	for(j = 0; j < B[0].size(); ++j)
        	{
                if(r_all0[i] || c_all0[j])
                    continue;
        		sum = 0;
        		for(k = 0; k < A[0].size(); ++k)
        			sum += A[i][k]*B[k][j];
        		ans[i][j] = sum;
        	}
        return ans;
    }
};

8 ms 8.6 MB

---

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！