212
技術社區[雲棲]
[LeetCode]73.Set Matrix Zeroes
【題目】
Given a m x n matrix,
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）的空間，但仍然不是最好的解決方案。
你可以製定一個連續的空間解決方案？
【分析】
- 思路1：
O(m + n) 空間的方法很簡單，設置兩個數組，記錄每行和每列是否存在 0。
- 思路2：
想要常數空間，可以複用第一行和第一列作為輔助空間使用。不用開辟新的存儲空間。其實第一行和第一列所在數組就是思路1中設置的數組，這樣減少空間開銷。
1.先確定第一行和第一列是否需要清零即，看看第一行中是否有0，記下來。也同時記下來第一列中有沒有0。
2.掃描剩下的矩陣元素，如果遇到了0，就將該行第一個元素和該列第一個元素賦值為0即賦值第一行數組和第一列數組。
這裏不用擔心會將本來第一行或第一列的1改成了0，因為這些值最後注定要成為0的。
3.根據第一行和第一列的信息，已經可以將剩下的矩陣元素賦值為結果所需的值了即，拿第一行為例，如果掃描到一個0，就將這一列都清0。
4.根據1中確定的狀態，處理第一行和第一列。如果最開始得到的第一行中有0的話，就整行清零。同理對列進行處理。
【代碼1】
/*********************************
* 日期：2014-01-23
* 作者：SJF0115
* 題號: Set Matrix Zeroes
* 來源：https://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
* 來源：https://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;
}
最後更新：2017-04-03 12:54:45