首页 > 试题广场 >

清除行列

[编程题]清除行列
  • 热度指数：29200 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

给定一个N阶方阵int[][](C++中为vector<vector><int>>)mat及其阶数n，若方阵中某个元素为0，则将其所在的行与列清零。返回改变后的int[][]方阵(C++中为vector<vector><int>>)，保证n小于等于300，矩阵中的元素在nt范围内。</int></vector></int></vector>

测试样例： 
[[1,2,3],[0,1,2],[0,0,1]]
返回：[[0,0,3],[0,0,0],[0,0,0]]
算法知识视频讲解
查看答案及解析
添加回答
推荐
luochangan头像 luochangan 

//楼上的Java版本有点复杂，写了个简单点的。
publicclassClearer {
    publicint[][] clearZero(int[][] mat, intn) {
        // write code here
        boolean[] rowArray = newboolean[n];
        boolean[] columnArray = newboolean[n];
         //记录为0的位置，把相应的行列位置设为true
        for(inti=0; i<n;i++)
        {
            for(intj=0;j<n;j++)
            {
                if(mat[i][j]==0)
                {
                    rowArray[i]=true;
                    columnArray[j]=true;
                }
            }         
        }
         //遍历找到之前记录的位置，把相应行列赋值为0
        for(inti=0;i<n;i++)
        {
            for(intj=0;j<n;j++)
            {
                if(rowArray[i]||columnArray[j])
                {
                mat[i][j] = 0;
                }
            }
        }
        returnmat;
    }
}

编辑于 2015-08-18 20:38:06 回复(15)
张佃鹏头像 张佃鹏

题目分析：

（1）题目陷阱：

一看到这个题目可能会想到遍历整个矩阵，只要发现值为0，就将其所在行和与列全部清零。这个是个错误的思想，当清零的时候，0元素覆盖了还没有遍历到的元素，所以只有数组有一个零，最后就导致整个数组全为0。

（2）思路一：

可以新建有一个同样大小矩阵标记零元素出现的位置，然后在第二次遍历矩阵时将0元素所在行与列清零，这样做的空间复杂度为0(MN)。

（3）思路二：

其实如果一行或者一列中不管是有一个零元素还是多个，这行都是要被删除的，所以我们定义两个数组分别表示行、列是否有零元素，在第一次遍历的时候，确定这两个数组，第二次遍历的时候，根据这两个数组的内容，将对应位置元素清零。所以这样所需要的存储空间是O(M+N)。
《程序员面试金典》程序详解：http://write.blog.csdn.net/postlist/5799903/all

（3）程序代码： 

 

class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
        // write code here
  if(mat.empty())
   return vector<vector<int> >();
  int len1=mat.size();
  int len2=mat[0].size();
  bool *sign1=new bool[len1]();
  bool *sign2=new bool[len2]();
  for(int i=0;i<len1;i++)
   for(int j=0;j<len2;j++)
    if(mat[i][j]==0)
    {
     sign1[i]=true;
     sign2[j]=true;
    }
  for(int i=0;i<len1;i++)
   for(int j=0;j<len2;j++)
    if(sign1[i]||sign2[j])
     mat[i][j]=0;
  return mat;
    }
};

编辑于 2015-09-15 19:47:01 回复(1)
穷极一生做不完一场梦头像 穷极一生做不完一场梦
为什么没人用HashSet呢？我感觉这么做挺简单的。  
public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        // write code here
        HashSet x = new HashSet();
        HashSet y = new HashSet();
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
            {
                if (mat[i][j] == 0) {
                    x.add(i);
                    y.add(j);
                }
            }
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (x.contains(i) || y.contains(j))
                    mat[i][j] = 0;
            }
        }
        return mat;
    }
}

编辑于 2015-11-21 11:55:27 回复(7)
Python
华科平凡头像 华科平凡

python solution:


class Clearer:
    def clearZero(self, mat, n):

        row=set()
        col=set()
        for i,v in enumerate(mat):
            for j,k in enumerate(v):
                if k==0:
                    row.add(i)
                    col.add(j)
        for i in row:
            for k in range(len(mat[0])):
                mat[i][k]=0
        for i in col:
            for k in range(len(mat)):
                mat[k][i]=0
        return mat
发表于 2017-10-03 17:44:57 回复(0)
忆水寒头像 忆水寒 
/*--------大家好，我是yishuihan------------
思路1，就是采用两个bool型数组，记录下有0 的行和列。然后分别清除行和列。
时间复杂度0（n^2），但是遍历了两遍，空间复杂度0（n）；
下面的方法2，空间复杂度进一步降低，只要两个变量解决问题,空间复杂度0（1）。*/
class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
        // write code here
        if(mat.size()<=0) return mat;
        //记录行和列的0
        bool* row=new bool[mat.size()];
        bool* col=new bool[mat[0].size()];
        //初始化一下
        for(unsigned int i=0;i<mat.size();i++)
            row[i]=false;
        for(unsigned int i=0;i<mat[0].size();i++)
            col[i]=false;
        //第一遍遍历元素，统计并标记0的行、列；
        for(unsigned int i=0;i<mat.size();i++)
        {
            for(unsigned int j=0;j<mat[0].size();j++)
            {
                if(mat[i][j]==0)
                {
                    row[i]=true;
                    col[j]=true;
                }
            }
        }
        //对应的位置置为0
        for(unsigned int i=0;i<mat.size();i++)
        {
            for(unsigned int j=0;j<mat[0].size();j++)
            {
                if(row[i]||col[j])
                    mat[i][j]=0;
            }
        }
        return mat;
    }
};
//思路2，首先处理第一行和第一列，看是否有0存在。
class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) 
    {
        // write code here
        if(mat.size()<=0) return mat;
        bool firstRow=false;
        bool firstCol=false;
        //扫描第一行，判断是否有0
        for(unsigned int i=0;i<mat[0].size();i++)
        {
            if(mat[0][i]==0)
            {
               firstRow=true; 
                break;
            } 
        }
        //扫描第一列，判断是否有0，为什么要单独判断呢，因为下面的处理....
        for(unsigned int j=0;j<mat.size();j++)
        {
            if(mat[j][0]==0)
            {
                firstCol=true;
                break;
            }
        }
        //主体处理
        for(unsigned int i=1;i<mat.size();i++)
        {
            for(unsigned int j=1;j<mat[0].size();j++)
            {
                if(mat[i][j]==0)
                {
                    mat[i][0]=0;
                    mat[0][j]=0;
                }
            }
        }
        //处理
        for(unsigned int i=1;i<mat.size();i++)
        {
            for(unsigned int j=1;j<mat[0].size();j++)
            {
                if(mat[i][0]==0||mat[0][j]==0)
                {
                   mat[i][j]=0;
                }
            }
        }
        if(firstRow)
        {
            for(unsigned int i=0;i<mat[0].size();i++)
            {
                   mat[0][i]=0;
            }
        }
        if(firstCol)
        {
            for(unsigned int i=0;i<mat.size();i++)
            {
                mat[i][0]=0;
            }
        }
        return mat;
    }
};

发表于 2016-08-08 14:53:25 回复(1)
牛客405621号头像 牛客405621号 
class Clearer {
public:
	vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
		// write code here
		vector<pair<int,int>> stc;    //保存横纵坐标
		for(int i = 0 ; i < n ;i++)	//每一行来一遍
		{
			for(int j = 0 ; j < n ; j++)	//每行中的各个元素
			{
				if(mat[i][j] == 0)
				{
					stc.push_back(pair<int,int>(i,j));
				}
			}
		}
		int row,col;
		for(int i = 0 ; i < stc.size() ;i++ )
		{
			//清除行
			row = stc[i].first;
			col = stc[i].second;
			for(int z = 0 ; z < n ; z++ )
			{
				mat[row][z] = 0 ;
				mat[z][col] = 0 ;
			}
		}
		return mat;
	}
};

发表于 2017-04-05 17:37:16 回复(0)
牛客712414号头像 牛客712414号
时间复杂度O(m*n)，空间复杂度为O(1).注意哦，空间复杂度为1 
import java.util.*;

public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        int x = 0;
        int y = 0;
        boolean frist = false;
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 0) {
                    if (!frist) {
                        x = i;
                        y = j;
                        frist = true;
                    } else {
                        mat[x][j] = 0;//对应的竖轴是否为0
                        mat[i][y] = 0;//对应的横轴是否为0
                    }
                }
            }
        }
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                if (i == x) {
                    break;
                } else if (j == y) {

                } else {
                    if (mat[x][j] * mat[i][y] == 0) {
                        mat[i][j] = 0;
                    }
                }
            }
        }
        for (int i = 0; i < mat.length; i++) {
            mat[i][y] = 0;
            mat[x][i] = 0;
        }
        return mat;
    }
}

发表于 2015-09-10 21:49:06 回复(3)
Ron头像 Ron 
import java.util.*;
/*此方法空间复杂度O(m+n)，时间复杂度O(m*n)，首先找到需要变为0的行和列号，
记录在矩阵rowZeros和colZeros中，若需要变为0则记为1，反之记为0，最后清零
*/
public class Clearer {
	public int[][] clearZero(int[][] mat, int n) {
		// write code here
		int M = mat.length;
		int N = mat[0].length;
		int[] rowZeros = new int[M];
		int[] colZeros = new int[N];
		for(int i = 0; i<M; i++){
			for(int j = 0;j<N;j++){
				if(mat[i][j]==0){
					rowZeros[i] = 1;
					colZeros[j] = 1;
				}
			}
		}
		for(int i=0;i<M;i++){
			for(int j=0;j<N;j++){
				if(rowZeros[i] == 1 || colZeros[j] == 1){
					mat[i][j] = 0;
				}
			}
		}
		return mat;
	}
}

发表于 2015-08-23 23:18:06 回复(1)
C/C++
N.A.头像 N.A. 
class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
        // write code here
        vector<vector<int>> mid=mat;
        vector<int> R(n,1);
        vector<int> C(n,1);
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if (mat[i][j]==0){
                    R[i]=0;
                    C[j]=0;
                }
            }
        }
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                mid[i][j]=mid[i][j]*R[i]*C[j];
            }
        }
        return mid;
    }
};

发表于 2017-06-11 21:33:29 回复(1)
nomico271头像 nomico271
遍历二维数组，若当前数字为0，就将其所在的行列标记。遍历数组结束后，将行列有标记的值均设为0。代码实现如下： 
import java.util.*;

public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        boolean[] rowArr = new boolean[n];
        boolean[] colArr = new boolean[n]; 
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (mat[i][j] == 0){
                    rowArr[i] = true;
                    colArr[j] = true;
                }
            }
        }
        
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (rowArr[i] || colArr[j]){
					mat[i][j] = 0;
                }
            }
        }
        
        return mat;
        
    }
}

发表于 2017-05-31 21:35:23 回复(0)
木然猫猫头像 木然猫猫 

# -*- coding:utf-8 -*-
class Clearer:
    def clearZero(self, mat, n):
        row = set()
        col = set()
        for r, m in enumerate(mat):
            for c, n in enumerate(m):
                if not n:
                    row.add(r)
                    col.add(c)
        for r in row:
            for i in range(len(mat[r])):
                mat[r][i] = 0
        for c in col:
            for i in range(len(mat)):
                mat[i][c] = 0
        return mat

发表于 2018-12-26 12:01:58 回复(0)
Salmon-William头像 Salmon-William
我的思路是：用一个[2]×[300]的矩阵去记录哪一行哪一列应该全是0；然后再进行分别对行和列（2*n）复杂度，进行赋0操作，这样就完成了。


class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > A, int n) {
        // write code here
        int B[2][300]={0};
           for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
     if(A[i][j]==0)
     {
      B[0][i]=1;
         B[1][j]=1;
     }
    }
    }
    for(int i=0;i<n;i++){
    if(B[0][i])
    {
    for(int j=0;j<n;j++){
         A[i][j]=0;   
        }
}    
    }
     for(int i=0;i<n;i++){
      if(B[1][i])
      {
      for(int j=0;j<n;j++){
         A[j][i]=0;   
        }
}  
    }
        return A;
    }
};
发表于 2017-08-26 19:37:38 回复(0)
阿狸不是猫头像 阿狸不是猫
import java.util.*;
//先统计元素为0的行与列，存放在另一个数组中
//统计完毕后，一次性清0
public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        HashSet<Integer> a=new HashSet<Integer> ();
        HashSet<Integer>  b=new HashSet<Integer> ();
        for(int i=0;i<n;i++){//统计元素为0的行与列
            for(int j=0;j<n;j++){
                if(mat[i][j] ==0){
a.add(i);
                    b.add(j);
                }
            }
        }
        for(int i:a){//根据行为0的情况清0
            for(int j=0;j<n;j++){
                mat[i][j] =0;
            }
        }
         for(int j:b){//根据列为0的情况清0
            for(int i=0;i<n;i++){
                mat[i][j] =0;
            }
        }
        return mat;
    } 
}
运行时间：377ms
占用内存：11584k
发表于 2017-05-16 14:40:46 回复(1)
Java
村长，那人偷牛！头像 村长，那人偷牛！ 
//自己想到的方法，跟大神的不谋而合，两个整形数组改成boolea数组为占用更小空间，懒得改了
public int[][] clearZero(int[][] mat, int n) {
       if(mat==null||n<=0) return mat;
       int[] column=new int[n];
       int[] row=new int[n];
       for(int i=0;i<n;i++){
           for(int j=0;j<n;j++){
               if(mat[i][j]==0){
                   row[i]=1;
                   column[j]=1;
               }  
           }
       }
       for(int i=0;i<n;i++){
           for(int j=0;j<n;j++)if(row[i]==1||column[j]==1) mat[i][j]=0;
       }
       return mat;
    }

编辑于 2017-05-11 00:30:28 回复(0)
李0810头像 李0810
class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
        int a[300][300]={0};
        for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(mat[i][j]==0){
                    a[i][j]=1;
                    }
            }
        for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(a[i][j]==1){
                    for(int k=0;k<n;k++){
                        mat[i][k]=0;
                        mat[k][j]=0;
                       }
                    }
            }
   return mat;
    }
};
发表于 2017-03-04 15:06:07 回复(0)
谭锅锅头像 谭锅锅 
# -*- coding:utf-8 -*-
class Clearer:
    def clearZero(self, mat, n):
        # write code here
        line = []
        row = []
        for i in range(n):
            for j in range(n):
                if mat[i][j] == 0:
                    if i not in line:
                        line.append(i)
                    if j not in row:
                        row.append(j)
        for i in range(n):
            for j in range(n):
                if i in line or j in row:
                    mat[i][j] = 0
        return mat
记录一下有那些行列有0就可以了额，

发表于 2016-12-05 21:32:19 回复(1)
冉承祥头像 冉承祥 
class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
       int *b1=new int[n];
       int *b2=new int[n];
       memset(b1,0,sizeof(b1));
       memset(b2,0,sizeof(b2));
       int i,j;
       for(i=0;i<n;i++)
         for(j=0;j<n;j++)
           if(!mat[i][j]) {b1[i]=1;b2[j]=1;}
       for(i=0;i<n;i++)
         for(j=0;j<n;j++)
           if(b1[i]==1||b2[j]==1) mat[i][j]=0; 
       return mat;
    }
};

发表于 2016-10-19 23:43:56 回复(0)
LuxSun头像 LuxSun 
public class Clearer {
    //如果碰到等于0的，则上下左右按理说都变0，但是避免接下来的判断，先判断要变的位置的值是否为0？true，则不变，false，则为-1（mark）。
	public int[][] clearZero(int[][] mat, int n) {
		int rows[]=new int[n*n];
		int cols[]=new int[n*n];
		Arrays.fill(rows, -1);
		Arrays.fill(cols, -1);
		int k=0;
		
//		System.out.println("#"+rows[0]+"#");
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int tn = mat[i][j];
				if(tn==0){
					rows[k]=i;
					cols[k++]=j;
				}
			}
		}
		
//		System.out.println(Arrays.toString(rows));
//		System.out.println(Arrays.toString(cols));
		
		int len=0;
		for (int i = 0; i < n; i++) {
			int tn = rows[i];
			if(tn!=-1){
				len++;
			}
			else{
				break;
			}
		}
		
		for (int i = 0; i < len; i++) {
			int row=rows[i];
			int col=cols[i];
			//竖
			for (int j = 0; j < n; j++) {
				int tn=mat[j][col];
				if(tn!=0){
					mat[j][col]=-1;
				}
			}
			//横
			for (int j = 0; j < n; j++) {
				int tn=mat[row][j];
				if(tn!=0){
					mat[row][j]=-1;
				}
			}
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(mat[i][j]==-1){
					mat[i][j]=0;
				}
			}
		}
		
		return mat;
	}
}
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为0.00%

测试用例:
[[84723,160966,131401,0,0,72950,0,99795,201933,206665,38068,51367,225028,148542,288421,175496,182352,239375,25268,14323,233117,171431,71668,91234,0,263829,179042,294483,69075,170720,174293,213328,223600,179091,106426,105929,99435,149216,152255,129819,188001,129488,299967,130,184790,123757,188528,20407,280655,26835,214087,278789,260645,47671,112374,0,55415,152144,172522,84307,206962,281718,277856,230486,143512,113588,233559,128422,268760,299980,112639,137909,5144,156944,222498,260480,89605,273657,182835,29155,222183,8566,222526,252186,206944,258665,92920,199875],[288850,235512,121764,294423,269365,211131,27366,199113,87645,159220,69497,45356,274445,64369,155646,210171,190059,254108,199755,197882,33121,282023,257627,158572,25810,134795,50231,230939,43104,190324,247033,122611,165231,148738,0,283931,77490,286081,147258,128799,242002,52104,151750,60209,0,217251,194719,176263,86562,160475,8802,32540,144238,19216,277285,218542,162773,32338,248197,122219,169802,106079,159508,110792,290534,48932,220154,
Q：系统也不提示我哪里错了。连我的输出都没  无语死。求大神带走~
发表于 2016-10-03 12:49:52 回复(0)
牛客8800022号头像 牛客8800022号 
请问这样写那个地方错了？？？？？
import java.util.*;
public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        // write code here
       Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < mat.length; i++) {
			for (int j = 0; j < mat.length; j++) {
				if(mat[i][j]==0){
					map.put(i, j);
				}
			}
		}
        for (int i = 0; i < mat.length; i++) {
			for (int j = 0; j < mat.length; j++) {
				if(map.containsKey(i)){
					mat[i][j]=0;
				}
			}
		}
        for (int i = 0; i < mat.length; i++) {
			for (int j = 0; j < mat.length; j++) {
				if(map.containsValue(i)){
					mat[j][i]=0;
				}
			}
		}
        return mat;
    }
}

发表于 2016-09-27 16:23:53 回复(0)
C/C++
玖玖头像 玖玖 
/*
时间复杂度O(n^2)，空间复杂度小于O(n^2)。
思路：①两层for循环记录元素为0的坐标；②得到全部元素为0的坐标后，则将其所在的行与列清零。
*/
class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) 
    {
        // write code here
        vector<pair<int, int> > temp;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
            	if(mat[i][j] == 0)
            		temp.push_back(make_pair(i,j));
        
        for(vector<pair<int, int> >::iterator it = temp.begin(); it != temp.end(); it++)
        {
            int x = (*it).first;
            int y = (*it).second;
            for(int i = x, j = 0; j < n; j++ )
                mat[i][j] = 0;
            for(int i = 0, j = y; i < n; i++ )
                mat[i][j] = 0;
        }
        
        return mat;
    }
};

编辑于 2016-09-03 11:50:35 回复(0)
Java
Rayley1900头像 Rayley1900 
import java.util.*;

public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        // write code here
        HashSet<Integer> xHash = new HashSet<>();
        HashSet<Integer> yHash = new HashSet<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j] == 0){
                    xHash.add(i);
                    yHash.add(j);
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(xHash.contains(i) || yHash.contains(j))
                    mat[i][j] = 0;
            }
        }
        return mat;
    }
}

发表于 2016-08-29 11:19:13 回复(0)
提交观点

问题信息

数组
难度：
158条回答 24034浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号