给定一个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]]
给定一个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]]
题目分析:
(1)题目陷阱:
一看到这个题目可能会想到遍历整个矩阵,只要发现值为0,就将其所在行和与列全部清零。这个是个错误的思想,当清零的时候,0元素覆盖了还没有遍历到的元素,所以只有数组有一个零,最后就导致整个数组全为0。
(2)思路一:
可以新建有一个同样大小矩阵标记零元素出现的位置,然后在第二次遍历矩阵时将0元素所在行与列清零,这样做的空间复杂度为0(MN)。
(3)思路二:
(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;
}
};
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;
}
}
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
/*--------大家好,我是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; } };
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; } };
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; } }
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; } }
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; } };
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; } }
# -*- 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
}
//自己想到的方法,跟大神的不谋而合,两个整形数组改成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; }
# -*- 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就可以了额,
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; } };
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; } }您的代码已保存
请问这样写那个地方错了????? 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; } }
/* 时间复杂度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; } };
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; } }