题解 | #矩阵元素相乘# 标记、预处理

主要考察预处理、对0的处理

使用行、列数组事先计算各行各列的乘积

使用标记数组标记好各行各列是否有0

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<vector<int>> matrix(n, vector<int>(m, 0)); // 存储矩阵信息
        vector<long> multiX(n, 1), multiY(m, 1); // 存储每行每列相乘的结果
        vector<bool> zeroX(n, false), zeroY(m, false); // 标志每行每列是否有0
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> matrix[i][j];
                // 如果读入0，标记行列，同时修改该值为-1，并跳过此循环
                if (matrix[i][j] == 0) {
                    zeroX[i] = true;
                    zeroY[j] = true;
                    matrix[i][j] = -1;
                    continue;
                }
                // 计算行列相乘结果
                multiX[i] *= matrix[i][j];
                multiY[j] *= matrix[i][j];
            }
        }
        long maxMulti = 1; // 保留最大乘积
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果 行或列有0 并且 矩阵值不是-1（即原矩阵的0），跳过
                if ((zeroX[i] || zeroY[j]) && matrix[i][j] != -1) {
                    continue;
                }
                // 比较并更新最大乘积，注意要除以矩阵值的平方
                maxMulti = max(maxMulti, multiX[i] * multiY[j] / (matrix[i][j] * matrix[i][j]));
            }
        }
        cout << maxMulti << endl;
    }
    return 0;
}

时间复杂度：O(mn)，用于遍历矩阵

空间复杂度：O(mn)，用于存储矩阵