济南网站建设-中国互联,网站开发配置状态统计,网站seo策划,重庆建设造价信息网站一.题目要求
给定一个 m x n 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
二.题目难度
中等
三.输入样例
示例 1#xff1a;
输入#xff1a;matrix [[1,1,1],[1,0,1],[1,1,1]] 输出#xff1a;[[1,0…一.题目要求
给定一个 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]]
提示 m matrix.length n matrix[0].length 1 m, n 200 − 2 31 -2^{31} −231 matrix[i][j] 2 31 − 1 2^{31} - 1 231−1
进阶 一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案。 一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案。 你能想出一个仅使用常量空间的解决方案吗
四.解题思路
没什么可说的 官方解法是优化后的
五.代码实现
class Solution {
public:void setZeroes(vectorvectorint matrix) {setint zeroh,zerol;vectorvectorint::iterator it;vectorint::iterator itt;for (it matrix.begin(); it ! matrix.end(); it){for (itt (*it).begin(); itt ! (*it).end(); itt){if (*itt 0){zeroh.insert(it - matrix.begin());zerol.insert(itt - (*it).begin());}}}for (setint::iterator it zeroh.begin(); it ! zeroh.end(); it){for (vectorint::iterator itl matrix[*it].begin(); itl ! matrix[*it].end(); itl){*itl 0;}}for (setint::iterator it zerol.begin(); it ! zerol.end(); it){for (vectorvectorint::iterator ith matrix.begin(); ith ! matrix.end(); ith){(*ith)[*it] 0;}}}
};官方给的优化方法
class Solution {
public:void setZeroes(vectorvectorint matrix) {bool firstRowZero false, firstColZero false;int rows matrix.size(), cols matrix[0].size();// Determine if the first row or first column is all zerosfor (int i 0; i rows; i) {if (matrix[i][0] 0) {firstColZero true;break;}}for (int j 0; j cols; j) {if (matrix[0][j] 0) {firstRowZero true;break;}}// Use first row and column as markers, set matrix[i][0] and matrix[0][j] to 0 if matrix[i][j] is 0for (int i 1; i rows; i) {for (int j 1; j cols; j) {if (matrix[i][j] 0) {matrix[i][0] 0;matrix[0][j] 0;}}}// Zero out cells based on the first row and columnfor (int i 1; i rows; i) {for (int j 1; j cols; j) {if (matrix[i][0] 0 || matrix[0][j] 0) {matrix[i][j] 0;}}}// Zero out the first row and column if neededif (firstColZero) {for (int i 0; i rows; i) matrix[i][0] 0;}if (firstRowZero) {for (int j 0; j cols; j) matrix[0][j] 0;}}
};六.题目总结
无
