408
CareerCup之1.7 Set Matrix Zeroes
【題目】
原文：
1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
譯文：
寫一個函數處理一個MxN的矩陣，如果矩陣中某個元素為0，那麼把它所在的行和列都置為0.
【分析】
【思路一】
遍曆一次矩陣，當遇到元素等於0時，記錄下這個元素對應的行和列。 可以開一個行數組row和列數組col，當元素a[i][j]等於0時， 就把row[i]和col[j]置為true。第二次遍曆矩陣時，當某個元素對應的行row[i] 或列col[j]被設置為true，說明該元素在需要被置0的行或列上，因此將它置0。
【思路二】
想要常數空間，可以複用第一行和第一列作為輔助空間使用。不用開辟新的存儲空間。其實第一行和第一列所在數組就是思路1中設置的數組，這樣減少空間開銷。
1.先確定第一行和第一列是否需要清零即，看看第一行中是否有0，記下來。也同時記下來第一列中有沒有0。
2.掃描剩下的矩陣元素，如果遇到了0，就將該行第一個元素和該列第一個元素賦值為0即賦值第一行數組和第一列數組。
這裏不用擔心會將本來第一行或第一列的1改成了0，因為這些值最後注定要成為0的。
3.根據第一行和第一列的信息，已經可以將剩下的矩陣元素賦值為結果所需的值了即，拿第一行為例，如果掃描到一個0，就將這一列都清0。
4.根據1中確定的狀態，處理第一行和第一列。如果最開始得到的第一行中有0的話，就整行清零。同理對列進行處理。
【代碼一】
/*********************************
* 日期：2014-05-15
* 作者：SJF0115
* 題目: Set Matrix Zeroes
* 來源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
void SetMatrixZeroes(int **matrix,int m,int n){
int i,j;
//初始化
int* col = new int(n+1);
int* row = new int(m+1);
memset(col,0,sizeof(int)*(n+1));
memset(row,0,sizeof(int)*(m+1));
//尋找0
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
if(matrix[i][j] == 0){
row[i] = col[j] = 1;
}//if
}//for
}//for
//0所在列和行全置為0
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
if(row[i] || col[j]){
matrix[i][j] = 0;
}//if
}//for
}//for
}
int main(){
int m,n,i,j;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d%d",&m,&n) != EOF){
if(m == 0 || n == 0){
break;
}
//初始化
int** matrix = new int*[m];
for(i = 0;i < m;i++){
matrix[i] = new int[n];
}
//輸入
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
cin>>matrix[i][j];
}
}
//置0
SetMatrixZeroes(matrix,m,n);
//輸出
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
【代碼二】
/*********************************
* 日期：2014-05-15
* 作者：SJF0115
* 題目: Set Matrix Zeroes
* 來源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
//Set Matrix Zeroes
void SetMatrixZeroes(int **matrix,int m,int n){
int i,j;
int firstRow = 0;
int firstCol = 0;
//判斷第一行是否有0
for(i = 0;i < n;i++){
if(matrix[0][i] == 0){
firstRow = 1;
}
}//for
//判斷第一列是否有0
for(i = 0;i < m;i++){
if(matrix[i][0] == 0){
firstCol = 1;
}
}//for
//搜索0進行標記
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
if(matrix[i][j] == 0){
matrix[i][0] = 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(firstRow){
for(i = 0;i < n;i++){
matrix[0][i] = 0;
}
}//if
//第一列存有0則全設置為0
if(firstCol){
for(i = 0;i < m;i++){
matrix[i][0] = 0;
}
}//if
}
int main(){
int m,n,i,j;
freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d%d",&m,&n) != EOF){
if(m == 0 || n == 0){
break;
}
//初始化
int** matrix = new int*[m];
for(i = 0;i < m;i++){
matrix[i] = new int[n];
}
//輸入
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
cin>>matrix[i][j];
}
}
//置0
SetMatrixZeroes(matrix,m,n);
//輸出
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
最後更新：2017-04-03 12:56:41