首页 > 试题广场 >

矩阵置0

[编程题]矩阵置0

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

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

拓展：

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

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

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

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

算法知识视频讲解

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)

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)

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)

Java

jRomann

import java.util.*;
public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        if(matrix==null || m==0 || n==0) return;
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==0) {
                list1.add(i);
                    list2.add(j);
                }
            }
        }
        while(list1.size()>0){
            int a = list1.remove(0);
            for(int j = 0;j<n;j++){
                matrix[a][j]=0;
            }
        }
        while(list2.size()>0){
            int a = list2.remove(0);
            for(int j = 0;j<m;j++){
                matrix[j][a]=0;
            }
        }
    }
}

发表于 2018-06-30 10:46:35 回复(0)

Java

PG.13

import java.util.*;
//思路：对应数字是0的行列分别存入map，键相同与否，做不同处理。
//通过得到的map去删除原来二维数组的行列。
public class Solution {
public void setZeroes(int[][] matrix) {
if(matrix==null){
return;
}
Map<Integer,ArrayList<Integer>>map = new HashMap<Integer,ArrayList<Integer>>();
int row = matrix.length;
int col = matrix[0].length;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(matrix[i][j]==0){
    ArrayList<Integer> list = new ArrayList<Integer>();
    if(!map.containsKey(i)){
        list.add(j);
        map.put(i, list);
    }else {
        ArrayList<Integer> arrayList = map.get(i);
        arrayList.add(j);
        map.put(i, arrayList);
                    }
}
}
}
subSet(map,matrix);
}
public void subSet(Map<Integer,ArrayList<Integer>>map,int[][]matrix){
    for(int key:map.keySet()){
        ArrayList<Integer> list = map.get(key);
        for (Integer integer : list) {
        for(int i=0;i<matrix.length;i++){
            matrix[i][integer]=0;
              }
              for(int i=0;i<matrix[0].length;i++){
                  matrix[key][i]=0;
              }
            }
    }
}
}

发表于 2017-10-30 14:35:42 回复(0)

Java

城市里的养猫者

My idea is simple: store states of each row in the first of that row, and store states of each column in the first of that column. Because the state of row0 and the state of column0 would occupy the same cell, I let it be the state of row0, and use another variable "col0" for column0. In the first phase, use matrix elements to set states in a top-down way. In the second phase, use states to set matrix elements in a bottom-up way.

void setZeroes(vector<vector<int> > &matrix) { int col0 = 1, rows = matrix.size(), cols = matrix[0].size(); for (int i = 0; i < rows; i++) { if (matrix[i][0] == 0) col0 = 0; for (int j = 1; j < cols; j++) if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
    } for (int i = rows - 1; i >= 0; i--) { for (int j = cols - 1; j >= 1; j--) if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0; if (col0 == 0) matrix[i][0] = 0;
    }
}

发表于 2017-03-12 12:00:52 回复(0)

Java

一枚后浪

同样的代码，第一次超时，第二次通过，牛客网的oj真是奇怪

发表于 2017-02-27 10:23:29 回复(0)

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)

Java

牛客262699号

import java.util.HashSet;
import java.util.Set;
public class Solution {
    //将数组中为0的点的下标分别存储在set中（不会重复），然后根据下标置0
    public void setZeroes(int[][] matrix) {
        if(matrix == null)
            return;
        int m = matrix.length;
        int n = matrix[0] .length;
        Set<Integer> setR = new HashSet<Integer>();
        Set<Integer> setC = new HashSet<Integer>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                if(matrix[i][j]==0){
                	setR.add(i);
                	setC.add(j);
            	}
        }
        for(int row:setR){
            for(int i=0;i<n;i++)
                matrix[row][i]=0;
        }
        for(int col:setC){
            for(int j=0;j<m;j++)
                matrix[j][col]=0;
        }
    }
}

发表于 2016-07-20 15:41:44 回复(1)