【题目】
Given amxnmatrix,
if an element is 0, set its entire row and column to 0. Do it in place.
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?
【题意】
给定一个mxn的矩阵,如果一个元素是0,则它的整个行和列都设置为0。在原矩阵上进行操作。
你有没有使用额外的空间?
直接使用为O(MN)的空间的方案可能并不是一个好的主意。
一个简单的改进方案需要O(M + N)的空间,但仍然不是最好的解决方案。
你可以制定一个连续的空间解决方案?
【分析】
O(m + n) 空间的方法很简单,设置两个数组,记录每行和每列是否存在 0。
想要常数空间,可以复用第一行和第一列作为辅助空间使用。不用开辟新的存储空间。其实第一行和第一列所在数组就是思路1中设置的数组,这样减少空间开销。
1.先确定第一行和第一列是否需要清零即,看看第一行中是否有0,记下来。也同时记下来第一列中有没有0。
2.扫描剩下的矩阵元素,如果遇到了0,就将该行第一个元素和该列第一个元素赋值为0即赋值第一行数组和第一列数组。
这里不用担心会将本来第一行或第一列的1改成了0,因为这些值最后注定要成为0的。
3.根据第一行和第一列的信息,已经可以将剩下的矩阵元素赋值为结果所需的值了即,拿第一行为例,如果扫描到一个0,就将这一列都清0。
4.根据1中确定的状态,处理第一行和第一列。如果最开始得到的第一行中有0的话,就整行清零。同理对列进行处理。
【代码1】
/*********************************
* 日期:2014-01-23
* 作者:SJF0115
* 题号: Set Matrix Zeroes
* 来源:http://oj.leetcode.com/problems/set-matrix-zeroes/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
//时间复杂度 O(m*n),空间复杂度 O(m+n)
void setZeroes(vector<vector<int> > &matrix) {
int i,j;
int m = matrix.size();
int n = matrix[0].size();
//标记该行是否存在0
vector<int> row(m,false);
//标记该列是否存在0
vector<int> col(n,false);
//搜索0标记行列
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
if(matrix[i][j] == 0){
col[j] = row[i] = true;
}//if
}//for
}//for
//如果某行存在0设置改行全为0
for(i = 0;i < m;i++){
if(row[i]){
//设置为0
for(j = 0;j < n;j++){
matrix[i][j] = 0;
}//for
}//if
}//for
//如果某列存在0设置改列全为0
for(i = 0;i < n;i++){
if(col[i]){
//设置为0
for(j = 0;j < m;j++){
matrix[j][i] = 0;
}//for
}//if
}//for
}
};
int main() {
Solution solution;
vector<int> row1 = {1,0,3,4};
vector<int> row2 = {9,4,0,2};
vector<int> row3 = {6,7,3,4};
vector<vector<int>> matrix;
matrix.push_back(row1);
matrix.push_back(row2);
matrix.push_back(row3);
solution.setZeroes(matrix);
int m = matrix.size();
int n = matrix[0].size();
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
return 0;
}
【代码2】
/*********************************
* 日期:2014-01-23
* 作者:SJF0115
* 题号: Set Matrix Zeroes
* 来源:http://oj.leetcode.com/problems/set-matrix-zeroes/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
//时间复杂度 O(m*n),空间复杂度 O(1)
void setZeroes(vector<vector<int> > &matrix) {
//标记第一行是否有0
bool rowZero = false;
//标记第一列是否有0
bool colZero = false;
int i,j;
int m = matrix.size();
int n = matrix[0].size();
//判断第一行是否有0
for(i = 0;i < n;i++){
if(matrix[0][i] == 0){
rowZero = true;
}//if
}//for
//判断第一列是否有0
for(i = 0;i < m;i++){
if(matrix[i][0] == 0){
colZero = true;
}//if
}//for
//搜索0进行标记
for(i = 1;i < m;i++){
for(j = 1;j < n;j++){
if(matrix[i][j] == 0){
matrix[i][0] = matrix[0][j] = 0;
}//if
}//for
}//for
for(i = 1;i < m;i++){
for(j = 1;j < n;j++){
if(matrix[i][0] == 0 || matrix[0][j] == 0){
matrix[i][j] = 0;
}//if
}//for
}//for
//第一行存有0则全设置为0
if(rowZero){
for(i = 0;i < n;i++){
matrix[0][i] = 0;
}
}//if
//第一列存有0则全设置为0
if(colZero){
for(i = 0;i < m;i++){
matrix[i][0] = 0;
}
}//if
}
};
int main() {
Solution solution;
vector<int> row1 = {1,2,3,4};
vector<int> row2 = {9,4,0,2};
vector<int> row3 = {6,7,3,4};
vector<vector<int>> matrix;
matrix.push_back(row1);
matrix.push_back(row2);
matrix.push_back(row3);
solution.setZeroes(matrix);
int m = matrix.size();
int n = matrix[0].size();
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
LeetCode 后端.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
Leetcode101.zip
刷leetcode总结.md
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
My Solutions to Leetcode problems. All solutions support C
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
LeetCode746.使用最小花费爬楼梯746. 使用最小花费爬楼梯解题思路:动态规划当前楼梯最小值=Math.min(前一步最小值,前两步最小值)简化 mi
LeetCode888. 公平的糖果棒交换888. 公平的糖果棒交换解题思路:哈希表法第一次遍历 A\B 计算二者的糖果差值 diff,同时以 B糖果值建立哈希
84. 柱状图中最大的矩形 - 力扣(LeetCode).html