首页 > 试题广场 >

矩阵置0

[编程题]矩阵置0

热度指数：10896 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个m*n的矩阵，如果有一个元素是0，就把该元素所在的行和列上的元素全置为0，要求使用原地算法。

拓展：

你的算法有使用额外的空间吗？

一种比较直接的算法是利用O(m,n)的空间，但是这不是一个好的解法

使用简单的改进可以在O(m+n)的空间解决这个问题，但是还不是最佳的解法

你能在常量级的空间复杂度内解决这个问题吗？

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        map<int,bool> row,col;
        for(int i=0;i<m;i++)
        	for(int j=0;j<n;j++)
        		if(matrix[i][j] == 0)
        			row[i] = col[j] = true;
		
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++)
			{
				if(row[i] || col[j])
					matrix[i][j] = 0;
			}
    }
};

发表于 2017-07-31 02:07:37 回复(0)

夕一啊

//找到0，把它所在行列里不为的都设为-1（这里假设了矩阵里只有正值，
//当然设置为一个不会出现的值就可以了） 
//找完之后遍历一次矩阵，把-1的全设置为0   
//不过这个算法是三个for循环的复杂度，有点大，但是也能通过 
class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        for(int i=0;i<n;i++)
            for(int j =0;j<m;j++){
                if(matrix[i][j]==0){
                    for(int k =0;k<n;k++)
                        if(matrix[k][j]!=0)
                            matrix[k][j] = -1;
                    for(int k =0;k<m;k++)
                        if(matrix[i][k]!=0)
                            matrix[i][k] = -1;
                }
            }
        for(int i=0;i<n;i++)
            for(int j =0;j<m;j++)
                if(matrix[i][j]==-1)
                    matrix[i][j] = 0;
    }
};

编辑于 2017-07-25 22:21:44 回复(2)

C/C++

QT菜鸡弟弟

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        int row = matrix.size();
        int colum = matrix[0].size();
        vector<vector<int> > vec;
        vector<int> v;
        if(row == 0||colum == 0)
            return;
        for(int i=0;i<row;i++)
            for(int j=0;j<colum;j++)
            {
                if(matrix[i][j]==0)
                {
                    v.push_back(i);
                    v.push_back(j);
                    vec.push_back(v);
                    v.clear();
                }
            }
        int size = vec.size();
        for(int i=0;i<size;i++)
        {
            for(int j=0;j<colum;j++)
            {
                matrix[vec[i][0]][j]=0;
            }
            for(int k=0;k<row;k++)
            {
                matrix[k][vec[i][1]]=0;
            }
        }
        return;
    }
};

发表于 2019-09-19 23:20:53 回复(0)

Java

华科平凡

Java 解法

思路很简单，在代码注释里都写好了。

import java.util.HashSet;

public class Solution {
    public void setZeroes(int[][] matrix) {
        // 创建两个集合，分别保存要重置为0的行与列
        HashSet<Integer> row = new HashSet();
        HashSet<Integer> col = new HashSet();
        // 遍历matrix，如果找到某数为0，将所在行与列存储到集合中。
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row.add(i);
                    col.add(j);
                }
            }
        }
        //将集合中保存的行数与列数分别遍历出来，分别将整行与整列置0
        for (Object num : row.toArray())
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[(int) num][i] = 0;
            }
        for (Object num : col.toArray())
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][(int) num] = 0;
            }
    }
}

发表于 2018-07-04 10:00:08 回复(2)

Thanksfornowcoder

首先，使用pair记录值为0的坐标；

然后，对值为0的坐标依次进行行和列的清零；over-ffg

    void setZeroes(vector<vector<int> > &matrix) {
        vector<pair<int,int>> vec;
        int m = matrix.size();
        int n = matrix[0].size();
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(matrix[i][j] == 0)
                    vec.push_back(make_pair(i, j));
        for(int i = 0; i < vec.size(); ++i){
            int x = vec[i].first;
            int y = vec[i].second;
            for(int j = 0; j < n;++j)
                matrix[x][j] = 0;
            for(int j = 0; j < m;++j)
                matrix[j][y] = 0;
        }
    }

发表于 2020-07-11 21:44:29 回复(0)

克伦特

通过两个一维数组记录要进行标记的行和列
class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        vector<int>hang;
        vector<int>lie;
        int m = matrix.size();
        int n = matrix[0].size();
        for(int i = 0;i<m;i++)
            for(int j = 0;j<n;j++)
                if(matrix[i][j]==0)
                {
                    hang.push_back(i);
                    lie.push_back(j);
                }
        int l1 = hang.size();
        int l2 = lie.size();
        for(int i =0;i<l1;i++)
            for(int j = 0;j<n;j++)
                matrix[hang[i]][j]=0;
        for(int i =0;i<l2;i++)
            for(int j = 0;j<m;j++)
                matrix[j][lie[i]]=0;
    }
};

发表于 2020-03-31 15:31:44 回复(0)

无心2019

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        vector<pair<int,int>>m;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==0)
                {
                    pair<int,int>p={i,j};
                    m.push_back(p);
                }
            }
        }
        for(int k=0;k<m.size();k++)
        {
            int x=m[k].first,y=m[k].second;
            for(int i=0;i<matrix.size();++i)
                matrix[i][y]=0;
            for(int j=0;j<matrix[0].size();++j)
                matrix[x][j]=0;
        }
    }
};

发表于 2019-05-17 09:48:50 回复(0)

Ybird

class Solution {
//使用第一行和第一列来记录行和列的置0情况
//想要记录它们自己是否要置0，只需要两个变量（一个是第一行，一个是第一列）就可以了。
//然后就是第一行和第一列，如果要置0，就把它的值赋成0（反正它最终也该是0，无论第一行或者第一列有没有0），否则保留原值。
//然后根据第一行和第一列的记录对其他元素进行置0。
//最后再根据前面的两个标记来确定是不是要把第一行和第一列置0就可以了。
//这样的做法只需要两个额外变量，所以空间复杂度是O(1)。
//时间上需要进行两次扫描，一次确定行列置0情况，一次对矩阵进行实际的置0操作，所以总的时间复杂度是O(m*n)
public:
    void setZeroes(vector<vector<int> > &matrix) {
        int rows = matrix.size();
        if(rows == 0) return;
        int cols = matrix[0].size();
        bool r0 = 0;
        for(int i = 0; i < rows; i++)
            if(matrix[i][0] == 0)
            {
                r0 = 1;
                break;
            }
        bool c0 = 0;
        for(int i = 0; i < cols; i++)
            if(matrix[0][i] == 0)
            {
                c0 = 1;
                break;
            }
        
        for(int i = 1; i < rows; i++)
        {
            for(int j = 1; j < cols; j++)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for(int i = 1; i < rows; i++)
        {
               for(int j = 1; j < cols; j++)
                 if(matrix[i][0] == 0 || matrix[0][j] == 0)   
                     matrix[i][j] = 0;
        }
        if(r0 == 1)
        for(int i = 0; i < rows; i++)
            matrix[i][0] = 0;
        if(c0 == 1)
        for(int i = 0; i < cols; i++)
            matrix[0][i] = 0;
    }
};

发表于 2017-08-19 16:58:56 回复(0)

LinuX18

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix)
    {
        unordered_set<int> rows;
        unordered_set<int> cols;
        int m=matrix.size(),n=matrix[0].size();
        for(int i =0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
               if(matrix[i][j]==0)
                {
                   rows.insert(i);
                   cols.insert(j);
               }
            }
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(rows.find(i) != rows.end() || cols.find(j) != cols.end())
                    matrix[i][j] = 0;
            }
        }
        return;
    }

};

发表于 2017-07-08 15:29:24 回复(1)

可乐猪

//时间复杂度O(mn)，空间复杂度O(1)
//利用第一行和第一列的空间做记录
class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        const int row = matrix.size();
        const int col = matrix[0].size();
        bool row_flg = false, col_flg = false;
        
        //判断第一行和第一列是否有零，防止被覆盖
        for (int i = 0; i < row; i++)
            if (0 == matrix[i][0]) {
            	col_flg = true;
            	break;
        	}
        for (int i = 0; i < col; i++)
            if (0 == matrix[0][i]) {
            	row_flg = true;
            	break;
        	}
        //遍历矩阵，用第一行和第一列记录0的位置
        for (int i = 1; i < row; i++)
            for (int j = 1; j < col; j++) 
            	if (0 == matrix[i][j]) {
            		matrix[i][0] = 0;
            		matrix[0][j] = 0;
        		}
        //根据记录清零
        for (int i = 1; i < row; i++)
            for (int j = 1; j < col; j++)
            	if (0 == matrix[i][0] || 0 == matrix[0][j])
            		matrix[i][j] = 0;
        //最后处理第一行
        if (row_flg)
            for (int i = 0; i < col; i++)
            	matrix[0][i] = 0;
        if (col_flg)
            for (int i = 0; i < row; i++)
            	matrix[i][0] = 0;
    }
};

发表于 2016-09-01 20:59:51 回复(6)

Java

詆調壹點

public class Solution {
    public void setZeroes(int[][] matrix) {
		boolean row = false,col=false;
		for (int i = 0; i < matrix[0].length; i ++ ) if(matrix[0][i] == 0) row = true;
		for (int i = 0; i < matrix.length; i ++ ) if(matrix[i][0] == 0) col = true;
		for (int i = 1; i < matrix.length; i ++ ) {
			for (int j = 1; j < matrix[0].length; j ++ ) {
				if(matrix[i][j] == 0) {
					matrix[0][j] = 0;
					matrix[i][0] = 0;
				}
			}
		}
		for (int i = 1; i < matrix.length; i ++ ) {
			for (int j = 1; j < matrix[0].length; j ++ ) {
				if(matrix[0][j]==0||matrix[i][0]==0) matrix[i][j] = 0;
			}
		}
		if(row) for (int i = 0; i < matrix[0].length; i ++ ) matrix[0][i] = 0;
		if(col) for (int i = 0; i < matrix.length; i ++ ) matrix[i][0] = 0;
	}
}

发表于 2016-11-06 14:15:34 回复(0)

C++

过客e

class Solution {
  public:
    void setZeroes(vector<vector<int> >& matrix) {
        vector<int>vi, vj;//定义两个数组分别存0位置的行标和列标
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == 0){
                    vi.push_back(i);
                    vj.push_back(j);
                }
                    
            }
        }

        for (int k = 0; k < vi.size(); k++) 
        {
            for (int i = 0; i < matrix.size(); i++) {//matrix.size()为矩阵的行数
                matrix[i][vj[k]]=0;//把0所在位置的那一列都赋值为0
            }
            for (int j = 0; j < matrix[0].size(); j++){//matrix[0].size()矩阵列数
                matrix[vi[k]][j]=0;//把0所在位置的那一行都赋值为0
            }
           
        }
            // cout<<matrix.size()<<"行"<<matrix[0].size()<<
            // "列"<<endl<<"有"<<vi.size()<<"个0元素"<<
            // "位置是"<<vi[0]<<","<<vj[0];
    }
};

发表于 2025-01-22 17:47:00 回复(0)

Java

波文

package com.zrar.arask.data.service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: tax2020
 * @description: 编程题
 * @author: fubowen
 * @create: 2021-02-22 09:16
 **/
public class Solution {
   static class point{
        private int x;
        private int y;

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }
    }

    public static void setZeroes(int[][] matrix) {
        //遍历矩阵 找到0的点 设置值为零
        //存0的点  坐标
        List<point> list=new ArrayList<>();
        for(int i=0;i<matrix.length;i++){
            int[] row=matrix[i];
            for(int j=0;j<row.length;j++){
                if(row[j]==0){
                    point point = new point();
                    point.setX(i);
                    point.setY(j);
                    list.add(point);            
                }
            }
        }
        int xlength=matrix[0].length;
        int ylength=matrix.length;
        for (point point : list) {
            for(int i=0;i<ylength;i++){
                matrix[i][point.getY()]=0;
            }
            for(int i=0;i<xlength;i++){
                matrix[point.getX()][i]=0;
            }
        }
    }
}

发表于 2021-02-24 10:01:46 回复(0)

C/C++

Clannad丶Fan

最朴素的思路了吧

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int i, j;
        set<int> set_m, set_n;
        for(i = 0;i < m;i++)
            for(j = 0;j < n;j++)
            {
                if(0 == matrix[i][j])
                {
                    set_m.insert(i);
                    set_n.insert(j);
                }
            }
        for(auto j = set_m.begin();j != set_m.end();j++)
        {
            for(int k = 0;k < n;k++)
                matrix[*j][k] = 0;
        }
        for(auto j = set_n.begin();j != set_n.end();j++)
        {
            for(int k = 0;k < m;k++)
                matrix[k][*j] = 0;
        }
    }
};

发表于 2021-02-20 12:41:44 回复(0)

Java

ppolarlllce

public class Solution {
public void setZeroes(int[][] matrix) {
int n=matrix.length;            //行
int m=matrix[0].length;        //列
//先遍历行n，再遍历列m
int[][] mat=new int[n][m];        //新建一个二维数组，用来做行列置零操作
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
mat[i][j]=matrix[i][j];
}

}//将数组赋值给新建数组

/*使用自建数组进行置零的操作的是为了防止在原数组上做操作时，

导致某些行列元素置零后影响到后面元素是否做行列置零的判断*/

for(int i=0;i<n;i++){
for(int j=0;j<m;j++){

if(matrix[i][j]==0){                      //找到原数组中为0的位置
for(int i1=0;i1<m;i1++){
mat[i][i1]=0;                    //将自建数组中为0的行置零
}
for(int i2=0;i2<n;i2++){
mat[i2][j]=0;                    //将自建数组中为0的列置零
}
}
}
}
//将自建数组中做了置零操作的行列赋值给元素组所对应的位置
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
matrix[i][j]=mat[i][j];
}
}
}
}

编辑于 2020-12-03 19:57:07 回复(0)

C/C++

华科不平凡

利用第一行和第一列存储状态：

首先记录第一行第一列中是否含有0
遍历矩阵，如果元素为0，将对应的行头和列头的元素置0
再次遍历矩阵，如果对应的行头或列头元素为0，将当前元素置0
最后，如果第一行原来就有0，将第一行置0，第一列同样操作

//
// Created by jt on 2020/9/25.
//
#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        bool firstRowHas0 = false, firstColHas0 = false;
        for (int i = 0; i < matrix.size(); ++i) {
            if (matrix[i][0] == 0) { firstColHas0 = true; break; }
        }
        for (int i = 0; i < matrix[0].size(); ++i) {
            if (matrix[0][i] == 0) { firstRowHas0 = true; break; }
        }
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0; matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < matrix.size(); ++i) {
            for (int j = 1; j < matrix[0].size(); ++j){
                if (matrix[0][j] == 0 || matrix[i][0] == 0) matrix[i][j] = 0;
            }
        }
        if (firstRowHas0) {
            for (int i = 0; i < matrix[0].size(); ++i) {
                matrix[0][i] = 0;
            }
        }
        if (firstColHas0) {
            for (int i = 0; i < matrix.size(); ++i) {
                matrix[i][0] = 0;
            }
        }
    }
};

发表于 2020-09-25 15:24:05 回复(0)

iMi丶

 public void setZeroes(int[][] matrix) {
        if(matrix == null){
            return;
        }
        
        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        boolean firstRow = false;
        boolean firstCol = false;
        //判断第一行是否存在0
        for(int i = 0; i < colLength; i++){
            if(matrix[0][i] == 0){
                firstRow = true;
                break;
            }
        }
        //判断第一列是否存在0
        for(int i = 0; i < rowLength; i++){
            if(matrix[i][0] == 0){
                firstCol = true;
                break;
            }
        }
        //遍历二行二列开始的二维数组
        for(int i = 1;i < rowLength; i++){
            for(int j = 1; j < colLength; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        //根据第一行置零, 需从1开始，否则如果matrix[0][0] = 0 会影响接下来第一列置零
        for(int i = 1;i < colLength; i++){
            if(matrix[0][i] == 0){
                for(int j = 1; j < rowLength;j++){
                    matrix[j][i] = 0;
                }
            }
        }
        //根据第一列置零，需从1开始，否则会被根据第一行置零结果影响，如果matrix[0][0] = 0
        for(int i = 1;i < rowLength; i++){
            if(matrix[i][0] == 0){
                for(int j = 1;j < colLength; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        //根据标志将一行一列置0
        if(firstRow){
            for(int i = 0;i < colLength; i++){
                matrix[0][i] = 0;
            }
        }
        if(firstCol){
            for(int i = 0;i < rowLength; i++){
                matrix[i][0] = 0;
            }
        }
    }

发表于 2020-07-15 10:37:29 回复(0)

kkk大人

思路：

利用第一行、第一列来标记，注意第一行、第一列被覆盖问题

1、先不处理第一行、第一列，只标记其一开始是否有0（row_flag, col_flag）；

2、然后从第二行第二列开始处理，若该位置为0，则将第一行、第一列对应位置置为0；

3、从第二行第二列开始，若其行列数对应第一行、第一列的值为0，则置0

4、若row_flag, col_flag为真，置0第一行，第一列

public class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col =matrix[0].length;
        boolean row_flag=false,col_flag=false;
        
        //利用第一行、第一列来标记
        //注意第一行、第一列被覆盖问题，先不处理第一行、第一列，只标记其一开始是否有0
        //第一行
        for(int j=0; j<col;j++)
        {
            if(matrix[0][j]==0)
            {
                row_flag=true;
                break;
            }
        }
        //第一列
        for(int i=0; i<row;i++)
        {
            if(matrix[i][0]==0)
            {
                col_flag=true;
                break;
            }
        }
        
        //第一行第一列置0
        for(int i=1;i<row;i++)
        {
            for(int j=1;j<col;j++)
            {
                if(matrix[i][j]==0)
                {
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        
        //对应行、列置0
        for(int i=1;i<row;i++)
        {
            for(int j=1;j<col;j++)
            {
                if(matrix[i][0]==0 || matrix[0][j]==0)
                {
                    matrix[i][j]=0;
                }
            }
        }
        
        if(row_flag==true)
        {
            for(int i=0;i<col;i++)
            {
                matrix[0][i]=0;
            }
        }
        if(col_flag==true)
        {
            for(int i=0;i<row;i++)
            {
                matrix[i][0]=0;
            }
        }
        
        
    }
}

发表于 2020-07-11 09:30:27 回复(0)

科学xx

public static void setZeroes(int[][] matrix) {
int[][] m = new int[matrix.length][matrix[0].length];
//先记录0的位置
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0 ){
m[i][j] = -1;
}
}
}
//根据记录的位置置为0
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[i].length; j++) {
if (m[i][j] == -1){
//行全置为0
for (int k = 0; k < matrix[i].length; k++) {
matrix[i][k] = 0;
}
//列全置为0
for (int k = 0; k < matrix.length; k++) {
matrix[k][j] = 0;
}
}
}
}
}

发表于 2020-06-19 20:23:59 回复(1)

实在学不动了

class Solution {
public:
    unordered_set<int> ST1,ST2;//ST1记住已经被发现的0的行坐标，ST2记住已经被发现的0的行坐标
    void setZeroes(vector<vector<int> > &matrix) {
        for(int i=0;i<matrix.size();i++) {
            for(int j=0;j<matrix[0].size();j++) {
                if(matrix[i][j]==0) {
                   if(ST1.find(i)==ST1.end()) ST1.insert(i);
                   if(ST2.find(j)==ST2.end()) ST2.insert(j);
                }
            }
        }
        for(unordered_set<int>::iterator i=ST1.begin();i!=ST1.end();i++) {
            for(int j=0;j<matrix[0].size();j++) {
                matrix[*i][j]=0;
            }
        }
        for(unordered_set<int>::iterator j=ST2.begin();j!=ST2.end();j++) {
            for(int i=0;i<matrix.size();i++) {
                matrix[i][*j]=0;
            }
        }
    }
};

发表于 2020-05-05 12:56:21 回复(0)