网站备案拍照背景图,上海网址建设公司,怎么让网站无法自适应,DS716 II 做网站题目
给定一个 m x n 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 示例 1#xff1a; 输入#xff1a;matrix [[1,1,1],[1,0,1],[1,1,1]]
输出#xff1a;[[1,0,1],[0,0,0],[1,0,1]]示例 2#xff1…题目
给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 示例 1 输入matrix [[1,1,1],[1,0,1],[1,1,1]]
输出[[1,0,1],[0,0,0],[1,0,1]]示例 2 输入matrix [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出[[0,0,0,0],[0,4,5,0],[0,3,1,0]] 分析
标记法
先判断第一行和第一列是否包含 0因为这两部分既是数据又充当标记作用。
遍历除第一行、第一列之外的所有元素。如果发现元素为 0则将对应行的第一列和对应列的第一行设为 0作为该行或该列需要清零的标记。
根据第一行和第一列的标记将相应的元素置为 0。这里需要跳过第一行和第一列因为它们需要后续单独处理。
根据最初的检查结果将第一行或第一列全部置为 0。
时间复杂度O()
空间复杂度O(1)
class Solution {
public:void setZeroes(vectorvectorint matrix) {if(matrix.empty() || matrix[0].empty()) return;int m matrix.size(), n matrix[0].size();bool firstRowZero false, firstColZero false;// 检查第一行是否有 0for (int j 0; j n; j) {if (matrix[0][j] 0) {firstRowZero true;break;}}// 检查第一列是否有 0for (int i 0; i m; i) {if (matrix[i][0] 0) {firstColZero true;break;}}// 用第一行和第一列记录每一行和每一列是否需要置 0for (int i 1; i m; i) {for (int j 1; j n; j) {if (matrix[i][j] 0) {matrix[i][0] 0; // 标记该行matrix[0][j] 0; // 标记该列}}}// 根据标记将对应行列置 0注意跳过第一行和第一列for (int i 1; i m; i) {for (int j 1; j n; j) {if (matrix[i][0] 0 || matrix[0][j] 0) {matrix[i][j] 0;}}}// 若第一行原本存在 0则将第一行全部置 0if (firstRowZero) {for (int j 0; j n; j) {matrix[0][j] 0;}}// 若第一列原本存在 0则将第一列全部置 0if (firstColZero) {for (int i 0; i m; i) {matrix[i][0] 0;}}}
};
