基础知识点
题目
给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：
对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。
返回 grid 的乘积矩阵。
示例 1：
输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。
示例 2：
输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。
感悟
原以为和MOD = 1000000007一样，直接使用封装好的此类，发现错误。赛场上时间紧急，来不及分析是两个不同的问题，还是我封装错误。只好使用笨办法。我记得1000000007是质数，才能转除为乘。考虑过12345是否是质数，当时觉判断烦恼，所以没判断。现在觉得很简单：以5结尾，就是5的倍数，不是质数。
分析
前缀和后缀和。第一轮的preRow记录[0,r) 所有元素的乘积，vLeft[r][c] 记录本行左边各元素的乘积，vRight[r][c]记录本行右边各元素的乘积。vRet[r][c]记录这三个的乘积。第二轮preRow记录[r+1,m_r)所有元素的乘积。第二轮vRet[r][c]乘以preRow就是结果。
测试用例
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
结果
| 当前数 | 前面行的乘积 | 前面行的乘积 | 左边乘积 | 右边乘积 |
| 1 | 1 | 4…9 | 1 | 6 |
| 2 | 1 | 4…9 | 1 | 3 |
| 3 | 1 | 4…9 | 2 | 1 |
| 4 | 6 | 7…9 | 1 | 30 |
| 5 | 6 | 7…9 | 4 | 6 |
| 6 | 6 | 7…9 | 20 | 1 |
| 7 | 1…6 | 1 | 1 | 72 |
| 8 | 1…6 | 1 | 7 | 9 |
| 9 | 1…6 | 1 | 56 | 1 |
解释
对{4,5,6}而言第一轮preRow是123=6，第二轮preRow是789。对4而言，left是1,right是30。对5而言，left是4,right是6。对6而言，left是20,right是1。
时间复杂度
O(n^2) 2轮，每轮2层循环，每层循环是O(n)。
代码
class Solution { public: vector<vector> constructProductMatrix(vector<vector>& grid) { m_r = grid.size(); m_c = grid.front().size(); //vLeft记录当前行，左边的成绩 vector<vector> vLeft(m_r, vector(m_c)), vRight(m_r, vector(m_c)), vRet(m_r, vector(m_c)); int iPreRow = 1; for (int r = 0; r < m_r; r++) { int pre = 1; for (int c = 0; c < m_c; c++) { vLeft[r][c] = pre; MulSelf(pre, grid[r][c]); } pre = 1; for (int c = m_c-1 ; c >= 0 ; c-- ) { vRight[r][c] = pre; MulSelf(pre, grid[r][c]); } for (int c = 0; c < m_c; c++) { vRet[r][c] = 1; MulSelf(vRet[r][c], iPreRow); MulSelf(vRet[r][c], vLeft[r][c]); MulSelf(vRet[r][c], vRight[r][c]); } MulSelf(iPreRow, pre); } iPreRow = 1; for (int r = m_r-1; r >= 0 ; r-- ) { int pre = 1; for (int c = 0; c < m_c; c++) { MulSelf(vRet[r][c], iPreRow); MulSelf(pre, grid[r][c]); } MulSelf(iPreRow, pre); } return vRet; } void MulSelf(int& self, int other) { const int MOD = 12345; self = ((long long)self * other) % MOD; } int m_r, m_c; };
一维化降低复杂度
分析
vLeft[r][c]记录 [0,r)行所有元素及r行[0,c)列元素的乘积，第二轮的pre记录(r,m_c)行所有元素及r行（c,m_c)列元素的乘积。
vLeft[1][1] = 1234 第二轮的pre = 9876
代码
class Solution { public: vector<vector> constructProductMatrix(vector<vector>& grid) { m_r = grid.size(); m_c = grid.front().size(); vector < vector> vLeft(m_r, vector(m_c)); int pre = 1; for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { vLeft[r][c] = pre; MulSelf(pre, grid[r][c]); } } vector<vector> vRet(m_r, vector(m_c)); pre = 1; for (int r = m_r-1 ; r >= 0 ;r–) { for (int c = m_c-1 ; c >= 0 ; c-- ) { const int index = m_c * r + c; vRet[r][c] = pre; MulSelf(vRet[r][c], vLeft[r][c]); MulSelf(pre, grid[r][c]); } } return vRet; } void MulSelf(int& self, int other) { const int MOD = 12345; self = ((long long)self * other) % MOD; } int m_r, m_c; };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector<vector>grid = { {1,2,3},{4,5,6} }; vector<vector> ans = { {720,360,240},{180,144,120} }; auto res = Solution().constructProductMatrix(grid); Assert(res, ans); grid = { {1,2,},{3,4},{5,6 }}; ans = { {720,360},{240,180},{144,120} }; res = Solution().constructProductMatrix(grid); Assert(res, ans); grid = { { 1,2,3,4,5,6 } }; ans = { { 720,360,240,180,144,120} }; res = Solution().constructProductMatrix(grid); Assert(res, ans); grid = { { 1},{2},{3},{4},{5},{6} }; ans = { { 720},{360},{240},{180},{144},{120} }; res = Solution().constructProductMatrix(grid); Assert(res, ans); CConsole::Out(res); }
其它
视频课程
要是你认为本篇难道较大，不好入手，推荐你先学习基础算法的课程，我已完成部分，余下部分持续更新中，就在CSDN学院。
https://edu.csdn.net/course/detail/38771
C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
相关下载
如果你想观其大略，建设下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
