【LeetCode】 Add to List 73. Set Matrix Zeroes

内容简介：【LeetCode】 Add to List 73. Set Matrix Zeroes

问题描述

https://leetcode.com/problems/set-matrix-zeroes/#/description

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

给定一个矩阵，如果一个元素为0，则其所在行和所在列都置为0.

注意：

乍一看很好解决——碰到一个为零的元素，就把它所在行列的其它元素置0就好了嘛，但实际一执行起来，就会有问题。因为如果就在原矩形上置0的话，最后的结果是整个矩阵都为0了。如下矩阵：

如果碰到matrix(0,0) = 0就把第一行和第一列都置为了0，然后的循环就会把所有的元素都置为0，得不出最终结果：

算法

不in-place，记录要置0的行列。 使用两个数组rows和cols，分别记录要置0的行、列，遍历一次矩阵，如果当前元素(i,j)为0，则rows[i]=true, cols[j]=true，遍历结束后再根据rows和cols将矩阵该置0的行、列置0。时间复杂度O(n ² )，空间复杂度O(m+n)。

代码

public void setZeroes(int[][] matrix) {
            if(matrix==null || matrix.length ==0) return;
            boolean[] rows = new boolean[matrix.length]; // 需要重置为0的行记为true，否则为false
            boolean[] cols = new boolean[matrix[0].length]; // 需要重置为0的列记为true，否则为false
            for(int i=0;i<matrix.length;i++) {
                for(int j=0;j<matrix[i].length;j++) {
                    if(matrix[i][j]==0) {
                        rows[i] = true;
                        cols[j] = true;
                    }
                }
            }
            for(int i=0;i<rows.length;i++) {
                if(rows[i])
                    row2zeros(matrix, i);
            }
            for(int j=0;j<cols.length;j++) {
                if(cols[j])
                    col2zeros(matrix,j);
            }
        }

        private void row2zeros(int[][] matrix, int row) {
            for(int i=0;i<matrix[row].length;i++) {
                matrix[row][i] = 0;
            }
        }

        private void col2zeros(int[][] matrix, int col) {
            for(int i=0;i<matrix.length;i++) {
                matrix[i][col] = 0;
            }
        }

转载请注明出处

：

http://www.zgljl2012.com/leetcode-add-to-list-73-set-matrix-zeroes/

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• 【LeetCode】 Add to List 73. Set Matrix Zeroes

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。