[CareerCup]Arrays and Strings―Q1.6

转载请注明出处：http://blog.csdn.net/ns_code/article/details/21480757

题目：

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的元素就直接把它所在的行和列的元素置为0，这样遍历到后面的0时就不知道该位置本来就是0还是后来被置为0的。我们可以在遇到0时，将其坐在行和列的元素置为一个数组中不存在的值，而后在第二次遍历的时候遇到该数值，就把它变为0，但这样的数值的选取不具有普遍性。

我们可以这样做，开辟两个bool数组row[M]和col[N]，各元素初始值均为false，当遍历矩阵A[M][N]时，遇到A[i][j]为0，则将row[i]和col[j]置为true，而后第二次遍历该矩阵时，遇到row[i]或col[j]为true的，就将第i行或第j列的元素置为0.

实现代码：

/*******************************************************
题目描述：
如果以m*n矩阵中某个元素为0，则将它所在的行和列都置为0
Date:2014-03-18
********************************************************/
#include
  
   
#include
   
     /* 由于我的编译器不支持C99，这里只能将数组row[m]和col[n]作为参数传入 */ void zeroMatrix(int (*A)[4],int *row,int *col,int m,int n) { int i,j; for(i=0;i