Set Matrix Zeroes
Given amxnmatrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m+n) space, but still not the best solution.
Could you devise a constant space solution?
利用额外空间O(m+n)的做法是很简洁的:
void setZeroes(vector<vector<int> > &matrix) {
int row = matrix.size();
if (row < 1) return;
int col = matrix[0].size();
vector<bool> colRecorder(col);
vector<bool> rowRecorder(row);
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (matrix[i][j] == 0)
{
rowRecorder[i] = true;
colRecorder[j] = true;
}
}
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (rowRecorder[i]) matrix[i][j] = 0;
else if (colRecorder[j]) matrix[i][j] = 0;
}
}
}
利用常数空间也可以:
就需要巧妙地利用原来矩阵的空间,这里利用第一行和第一列保存额外信息:
1 先判断号第一行和第一列是否需要全部置零
2 有任何一个该行或者该列的元素为零那么这个第一行或者第一列的元素必然是零,就保存这个零,最后用来判断整个矩阵的这一行或者这一列是否需要置零。
3 最后再根据前面判断,决定是否把这个第一行和第一列置零。
void setZeroes2(vector<vector<int> > &matrix)
{
int row = matrix.size();
if (row < 1) return;
int col = matrix[0].size();
bool firstRowhasZero = false;
bool firstColhasZero = false;
for (int i = 0; i < row && !firstColhasZero; i++)
if (matrix[i][0] == 0) firstColhasZero = true;
for (int i = 0; i < col && !firstRowhasZero; i++)
if (matrix[0][i] == 0) firstRowhasZero = true;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (matrix[i][j] == 0)
{
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
//注意:这里从1开始
for (int i = 1; i < row; i++)
{
for (int j = 1; j < col; j++)
{
if (matrix[i][0] == 0) matrix[i][j] = 0;
else if(matrix[0][j] == 0) matrix[i][j] = 0;
}
}
if (firstColhasZero)
{
for (int i = 0; i < row; i++)
{
matrix[i][0] = 0;
}
}
if (firstRowhasZero)
{
for (int i = 0; i < col; i++)
{
matrix[0][i] = 0;
}
}
}
和上面差不多,小小改动一下。
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix)
{
int row = matrix.size();
if (row < 1) return;
int col = matrix[0].size();
bool firstRowhasZero = false;
bool firstColhasZero = false;
for (int i = 0; i < row; i++)
if (matrix[i][0] == 0)
{
firstColhasZero = true;
break;
}
for (int i = 0; i < col; i++)
if (matrix[0][i] == 0)
{
firstRowhasZero = true;
break;
}
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (matrix[i][j] == 0)
{
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < row; i++)
{
if (matrix[i][0] == 0)
for (int j = 1; j < col; j++)
{
matrix[i][j] = 0;
}
}
for (int j = 1; j < col; j++)
{
if (matrix[0][j] == 0)
for (int i = 1; i < row; i++)
{
matrix[i][j] = 0;
}
}
if (firstColhasZero)
{
for (int i = 0; i < row; i++)
{
matrix[i][0] = 0;
}
}
if (firstRowhasZero)
{
for (int i = 0; i < col; i++)
{
matrix[0][i] = 0;
}
}
}
};
//2014-2-11 update
void setZeroes(vector<vector<int> > &matrix)
{
if (matrix.empty() || matrix[0].empty()) return;
bool row_flag = false, col_flag = false;
for (int i = 0; i < matrix.size() && !col_flag; i++)
if (matrix[i][0]==0) col_flag = true;
for (int i = 0; i < matrix[0].size() && !row_flag; i++)
if (matrix[0][i]==0) row_flag = true;
for (int i = 1; i < matrix.size(); i++)
for (int j = 1; j < matrix[0].size(); j++)
if (matrix[i][j]==0) matrix[i][0] = matrix[0][j] = 0;
for (int i = 1; i < matrix.size(); i++)
if (matrix[i][0]==0)
for (int j = 1; j < matrix[0].size(); j++)
matrix[i][j] = 0;
for (int j = 1; j < matrix[0].size(); j++)
if (matrix[0][j]==0)
for (int i = 1; i < matrix.size(); i++)
matrix[i][j] = 0;
if (row_flag)
for (int i = 0; i < matrix[0].size(); i++)
matrix[0][i] = 0;
if (col_flag)
for (int i = 0; i < matrix.size(); i++)
matrix[i][0] = 0;
}
分享到:
相关推荐
378.Kth_Smallest_Element_in_a_Sorted_Matrix有序矩阵中第K小的元素【LeetCode单
题目来源:https://leetcode-cn.com/problems/01-matrix 题目 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 示例 1: 输入: 0 0 0 0 1 0 0 0 0 输出: 0 0 0 0 1 0 ...
leetcode生成斜矩阵 Leetcode Leetcode刷题记录 [toc] 1 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。...
示例 1:输入:[[1,2,3],[4,5,6],[7,8,9]]输出:[[1,4,7],[2,5,8],[3,6,9]]示例 2:输入:[[1,2,3],[4
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
复杂度分析时间复杂度:O(NM)空间复杂度:O(1)代码实现j++ { // 单独记录并处理第一行row0 = true // 标记第一行含有0i++ { //
扩展矩阵leetcode leetcode 岛屿数量: 问题陈述: Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting ...
javascript javascript_leetcode面试题解递归与回溯问题之第73题矩阵置零_题解
矩阵置零的题目如下图,核心把矩阵中当前0元素所在的行和列都重置为0,并且只能在当前矩阵上改动,不能新建矩阵,所以要使用下标进行标记,并最终重新赋值。 原创文章 40获赞 41访问量 2万+ 关注 私信 展开...
如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素,那么这个矩阵是托普利茨矩阵。 给定一个 M x N 的矩阵,当且仅当它是托普利茨矩阵时返回 True。 示例 1: 输入: matrix = [ [1,2,3,4], [5,1,2,3], [9...
python矩阵置零(leetcode)(csdn)————程序
矩阵中的元素只在四个方向上相邻: 上、下、左、右思路1首先是中规中矩的思路, 对每一个0值做BFS广度优先遍历, 以下值实际代码需要注意的是matrix[x]
leetcode中文版
vs code LeetCode 插件
扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 maxArea 26.删除排序数组中的重复项 removeDuplicates 33.搜索旋转排序数组 search 34.在排序数组中查找元素的第一个和最后一个位置 search...
蛇形矩阵leetcode dingjianhub 的 leetcode 题解 写在前面 这里是 的 leetcode 刷题的笔记。 包含了已经提交的题目的代码、笔记。有些笔记较为详细,有些较为简略。 在这些笔记中,很多内容是参考、摘录、再创作了很...
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
0867. 转置矩阵标签:数组难度:简单题目大意给定一个二维数组 matrix。返回 matrix 的转置矩阵。根据转置的规则对 transposed 的每个元
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip