leetcode 73. 矩阵置零

栏目: IT技术 · 发布时间: 4年前

内容简介:给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。示例 1:输入:

给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 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]

]

进阶:

一个直接的解决方案是使用  O(mn) 的额外空间,但这并不是一个好的解决方案。

一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。

你能想出一个常数空间的解决方案吗?

思路:利用第一行和第一列记录这一行/列有没有0即可。

(但是要特殊照顾第一行和第一列)

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        // 第一行是否有零
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        // 第一列是否有零
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }
        // 把第一行第一列作为标志位
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][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 (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        } 
    }
}

以上所述就是小编给大家介绍的《leetcode 73. 矩阵置零》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

从“为什么”开始

从“为什么”开始

[美] 西蒙·斯涅克 / 苏西 / 海天出版社 / 2011-7 / 32.00元

影响人类的行为:要么靠操纵,要么靠感召。 操纵带来的是交易,是短期效益; 感召带来的是信任,是永续经营! 盖茨走后,微软面临怎样的挑战?后盖茨时代,微软为何从一个希望改变世界的公司沦落为一个做软件的公司? 沃尔玛的灵魂人物过世后,一度被人们热爱的公司,遭到的竟然多是顾客、员工的反感?沃尔玛要怎样做才能重放昔日光彩? 星巴克吸引人们购买的不是咖啡,而是理念?为什么说霍华......一起来看看 《从“为什么”开始》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具