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. 矩阵置零》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

PHP经典实例(第3版)

PHP经典实例(第3版)

David Sklar、Adam Trachtenberg / 苏金国、丁小峰 / 中国电力出版社 / 2015-7 / 128.00

想要掌握PHP编程技术?或者想要学习如何完成一个特定的任务?那么一定要先看看《PHP经典实例(第3版)》。本书介绍了专门为PHP 5.4和5.5修订的350个经典技巧,并提供了丰富的示例代码。特别是对生成动态Web内容的解决方案做了全面更新,从使用基本数据类型到查询数据库,从调用RESTful API到测试和保护网站安全都有涵盖。 各个技巧都提供了示例代码,可以免费使用,另外还讨论了如何解决......一起来看看 《PHP经典实例(第3版)》 这本书的介绍吧!

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

Markdown 在线编辑器

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

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

HSV CMYK互换工具