package arrays;

/**题目:矩阵置零
 * 给定一个m*n的二维数组,如果某个位置(i,j)的值为0,
 * 那么就把第i行和第j列的元素都置为零
 * @Author Gavin
 * @date 2022年01月02日 22:42
 */
public class array_9 {
 /**
 * 第一种方法:通过for循环来处理
 */
 //Time:O(m*n) Space:O(m+n)
 public void solution_1(int[][] a){
 int m=a.length,n=a[0].length;
 boolean[] rows=new boolean[m];//存储某行是否应该置0
 boolean[] cols=new boolean[n];//存储某列是否应该置为0
 for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
 if(a[i][j]==0){
 rows[i]=cols[j]=true;
 }
 }
 }
 for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
 if(rows[i]||cols[j]){
 a[i][j]=0;
 }
 }
 }
 }
 /**
 * 第二种方法
 */
 //Time:O(m*n) Space:O(1)
 public void solution_2(int[][] a){
 int m=a.length,n=a[0].length;
 boolean row0=false,col0=false;

 for (int i = 0; i < m; i++) {
 if(a[i][0]==0)col0=true;
 }
 for (int i = 0; i < n; i++) {
 if(a[0][i]==0)row0=true;
 }

 for (int i = 1; i < m; i++) {
 for (int j = 1; j <n ; j++) {
 if(a[i][j]==0){
 a[i][0]=a[0][j]=0;
 }
 }
 }
 for (int i = 1; i < m; i++) {
 for (int j = 1; j <n ; j++) {
 if(a[i][0]==0||a[0][j]==0){
 a[i][j]=0;
 }
 }
 }
 if(row0){
 for (int i = 0; i < n; i++) {
 a[0][i]=0;
 }
 }
 if(col0){
 for (int i = 0; i < n; i++) {
 a[i][0]=0;
 }
 }
 }
}