当前位置:网站首页>面试题 01.08. 零矩阵
面试题 01.08. 零矩阵
2022-07-04 21:23:00 【Mr Gao】
面试题 01.08. 零矩阵
编写一种算法,若M × N矩阵中某个元素为0,则将其所在的行与列清零。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
void dfs(int **matrix,int n ,int m,int row,int col,int *rrow,int* rcol ){
int i;
// printf("- %d %d ",col,row);
if(rrow[row]==1){
rrow[row]=0;
for(i=0;i<m;i++){
if(matrix[row][i]!=0){
matrix[row][i]=-999;
}
else{
if(rrow[row]==1||rcol[i]==1){
dfs(matrix,n , m, row, i,rrow,rcol);
}
}
}
}
if(rcol[col]==1){
rcol[col]=0;
for(i=0;i<n;i++){
if(matrix[i][col]!=0){
matrix[i][col]=-999;
}
else{
if(rrow[i]==1||rcol[col]==1){
dfs(matrix, n , m, i, col,rrow,rcol);
}
}
}
}
}
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
int n=matrixSize;
int m=matrixColSize[0];
int *rrow=(int *)malloc(sizeof(int)*n);
int *rcol=(int *)malloc(sizeof(int)*m);
int i,j;
for(i=0;i<n;i++){
rrow[i]=1;
}
for(i=0;i<m;i++){
rcol[i]=1;
}
printf("df");
for(i=0;i<n;i++){
if(rrow[i]==1){
for(j=0;j<m;j++){
if(matrix[i][j]==0){
dfs(matrix,n , m, i, j,rrow,rcol);
break;
}
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(matrix[i][j]==-999){
matrix[i][j]=0;
}
}
}
}
这里也有一种比较简单的算法,标记出现过0的行和列,然后进行遍历那个那两个存储存储行和列的数组,这种方法就比较简单了
边栏推荐
猜你喜欢
Daily question-leetcode556-next larger element iii-string-double pointer-next_ permutation
How to remove the black dot in front of the title in word document
el-tree结合el-table,树形添加修改操作
【C语言】符号的深度理解
Enlightenment of maker thinking in Higher Education
Analyzing the maker space contained in steam Education
[weekly translation go] how to code in go series articles are online!!
[early knowledge of activities] list of recent activities of livevideostack
Redis 排查大 key 的3种方法,优化必备
Arcgis 10.2.2 | arcgis license server无法启动的解决办法
随机推荐
QT - double buffer plot
Bookmark
Redis has three methods for checking big keys, which are necessary for optimization
[C language] deep understanding of symbols
Daily question -leetcode1200- minimum absolute difference - array - sort
GTEST from ignorance to proficiency (4) how to write unit tests with GTEST
EhLib 数据库记录的下拉选择
Solve the problem of data disorder caused by slow asynchronous interface
置信区间的画法
什么是商业智能(BI),就看这篇文章足够了
Minidom module writes and parses XML
[buuctf.reverse] 151_ [FlareOn6]DnsChess
关系型数据库
旋变串判断
Redis03 - network configuration and heartbeat mechanism of redis
[weekly translation go] how to code in go series articles are online!!
QT - plot other problems
How was MP3 born?
How is the entered query SQL statement executed?
MongoDB聚合操作总结