首页 > 试题广场 >

矩阵置0

[编程题]矩阵置0
  • 热度指数:10862 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个m*n的矩阵,如果有一个元素是0,就把该元素所在的行和列上的元素全置为0,要求使用原地算法。
拓展:
你的算法有使用额外的空间吗?
一种比较直接的算法是利用O(m,n)的空间,但是这不是一个好的解法
使用简单的改进可以在O(m+n)的空间解决这个问题,但是还不是最佳的解法
你能在常量级的空间复杂度内解决这个问题吗?
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)
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)
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 解法

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

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)
首先,使用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)
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)
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)

 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)
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)
最朴素的思路了吧
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)

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)

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

  • 首先记录第一行第一列中是否含有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)
 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)

思路:

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

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)
  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)
import java.util.*;

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return ;
        Set<Integer> rows = new HashSet<>(), cols = new HashSet<>();
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        for (Integer row : rows)
            Arrays.fill(matrix[row], 0);
        for (Integer col : cols) {
            for (int i = 0; i < m; i++)
                matrix[i][col] = 0;
        }
    }
}
发表于 2020-02-23 17:50:54 回复(0)