`
bcyy
  • 浏览: 1809320 次
文章分类
社区版块
存档分类
最新评论

Set Matrix Zeroes -- LeetCode

 
阅读更多
原题链接:http://oj.leetcode.com/problems/set-matrix-zeroes/
这是一个矩阵操作的题目,目标很明确,就是如果矩阵如果有元素为0,就把对应的行和列上面的元素都置为0。这里最大的问题就是我们遇到0的时候不能直接把矩阵的行列在当前矩阵直接置0,否则后面还没访问到的会被当成原来是0,最后会把很多不该置0的行列都置0了。
一个直接的想法是备份一个矩阵,然后在备份矩阵上判断,在原矩阵上置0,这样当然是可以的,不过空间复杂度是O(m*n),不是很理想。
上面的方法如何优化呢?我们看到其实判断某一项是不是0只要看它对应的行或者列应不应该置0就可以,所以我们可以维护一个行和列的布尔数组,然后扫描一遍矩阵记录那一行或者列是不是应该置0即可,后面赋值是一个常量时间的判断。这种方法的时间复杂度是O(m+n)。
其实还可以再优化,我们考虑使用第一行和第一列来记录上面所说的行和列的置0情况,这里问题是那么第一行和第一列自己怎么办?想要记录它们自己是否要置0,只需要两个变量(一个是第一行,一个是第一列)就可以了。然后就是第一行和第一列,如果要置0,就把它的值赋成0(反正它最终也该是0,无论第一行或者第一列有没有0),否则保留原值。然后根据第一行和第一列的记录对其他元素进行置0。最后再根据前面的两个标记来确定是不是要把第一行和第一列置0就可以了。这样的做法只需要两个额外变量,所以空间复杂度是O(1)。
时间上来说上面三种方法都是一样的,需要进行两次扫描,一次确定行列置0情况,一次对矩阵进行实际的置0操作,所以总的空间复杂度是O(m*n)。代码如下:
public void setZeroes(int[][] matrix) {
    if(matrix==null || matrix.length==0 || matrix[0].length==0)
        return;
    boolean rowFlag = false;
    boolean colFlag = false;
    for(int i=0;i<matrix.length;i++)
    {
        if(matrix[i][0]==0)
        {
            colFlag = true;
            break;
        }
    }
    for(int i=0;i<matrix[0].length;i++)
    {
        if(matrix[0][i]==0)
        {
            rowFlag = true;
            break;
        }
    }      
    for(int i=1;i<matrix.length;i++)
    {
        for(int j=1;j<matrix[0].length;j++)
        {
            if(matrix[i][j]==0)
            {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    for(int i=1;i<matrix.length;i++)
    {
        for(int j=1;j<matrix[0].length;j++)
        {
            if(matrix[i][0]==0 || matrix[0][j]==0)
                matrix[i][j] = 0;
        }
    }
    if(colFlag)
    {
        for(int i=0;i<matrix.length;i++)
        {
            matrix[i][0] = 0;
        }
    }
    if(rowFlag)
    {
        for(int i=0;i<matrix[0].length;i++)
        {
            matrix[0][i] = 0;
        }
    }
}
这道题也是cc150里面比较经典的题目,看似比较简单,却可以重重优化,最终达到常量空间。其实面试中面试官看重的是对于算法时间空间复杂度的理解,对优化的概念,这些常常比题目本身的难度更加重要,平常做题还是要对这些算法分析多考虑哈。
分享到:
评论

相关推荐

    leetcodelintcode差异-leetcode-python:leetcode-python

    Zeroes Array、Two Pointers Array、Two Pointers LeetCode 120. Triangle LintCode 382. Triangle Count/LeetCode 611. Valid Triangle Number LeetCode 18. 4Sum (LeetCode 86. Partition List) LintCode 373. ...

    leetcode1004-leetcode:leetcode

    Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E) 653. Two Sum IV - Input is a BST (E) -&gt; 2 26. Remove Duplicates from Sorted Array (E) 27. Remove Element (E) 31. Next ...

    leetcode提交记录消失-leetcode-java:我对leetcode问题的解决方案

    leetcode提交记录消失解决...https://leetcode.com/problems/factorial-trailing-zeroes/description/ first-submission-successful : no 2018-05-05 : - id : 70 type : dynamic-programming difficulty : easy url

    leetcode卡-leetcode:利特码解决方案

    Matrix Zeroes API System.arrayCopy 刷题顺序 TOP100 其中算法,主要是以下几种: 基础技巧:分治、二分、贪心 排序算法:快速排序、归并排序、计数排序 搜索算法:回溯、递归、深度优先遍历,广度优先遍历,二叉...

    leetcode刷题账号-leetcode:leetcode

    LeetCode 题目我会定时更新一些,数组、链表、栈、队列、二叉树等经典题目 解法会从遍历、递归、动态规划等逐步展开 刷题步骤 修改自己的刷题群备注为自己的 Coding 账号名称,例如 codedrinker 克隆项目到本地,...

    leetcode中国-leetcode:刷算法了

    Set Matrix Zeroes 第一种 通过一次遍历记录所有为0的索引(Python中enumerate()输出当前列表的索引) 再遍历一次, 根据记录的索引进行置0 第二种 通过一次遍历所有为0的索引, 设置当前索引的行列的第一个数为0, 作为...

    最大公共字符串leetcode-Leetcode.DataStructure-notes:Leetcode之分类刷题之数据结构部分~

    最大公共字符串leetcode Leetcode.DataStructure-notes Leetcode之分类刷题之数据结构部分~ No-&gt;1.数组与矩阵↓↓↓↓↓↓↓↓↓↓ 109.83. Move Zeroes (Easy):1.把数组中的0移到末尾 例如,给定nums = [0,1,0,3,...

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    判断链表是否为回文链表leetcode-LeetCode:LeetCode刷题

    5.MoveZeroes 移动零:给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 6.PlusOne 加一:给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 7.Remove...

    leetcode算法题主函数如何写-leetcode:leetcode

    Matrix Zeroes 将第一行(或第一列)作为标志,第一行(或第一列)用其他标志。 从$(0, 0)$到$(m-1, n-1)$前向遍历将标志置0,从$(m-1, n-1)$到$(0, 0)$逆序遍历按标志将元素置0。时间复杂度$O(MN)$。 535: Encode and ...

    leetcode信封-leetcode:leetcode

    leetcode信封 leetcode 目前所完成的leetcode题目 还有部分lintcode题目 Tips 加速输入 int x=[](){ std::ios::sync_with_stdio(false);...Zeroes* 51.5% 448 Find All Numbers Disappeared in an Array* 51.2% 717

    lrucacheleetcode-leetcode:记录自己的leetcode解题历程~Welcomeeveryonetocomment:grinning_face:~

    Set Matrix Zeroes 48. Rotate Image 344. Reverse String 414. Third Maximum Number 448. Find All Numbers Disappeared in an Array 66. Plus One 238. Product of Array Except Self 697. Degree of an ...

    zeroes-crx插件

    语言:English 查找任何二次函数的零。 简单的。 一个简单的chrome扩展名,可帮助您在浏览器中找到二次方程的x截距。 有助于进行数学测试,或者只是在您喜欢那些甜美的零甜食时!

    leetcode中国-LeetCode:LeetCode题解,Python

    leetcode中国 LeetCode 题解 数组与矩阵 把数组中的 0 移到末尾 解题思路: 方法一: 首先想到的是可以利用冒泡的思想,将等于 0 的元素依次挪到最后。这里有个优化,每次都判断下是否有元素交换,如果没有交换则...

    Leetcode的ac是什么意思-LeetCodeInJava:leetcode-java

    Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...

    leetcode跳跃-LeetCode:力扣刷题70道!

    Zeroes 力扣 27 移除元素 | Remove Element 链表 Linked List 力扣 203 移除链表元素 | Remove Linked List Elements 力扣 206 反转链表 | Reverse Linked List 队列 Queue 力扣 933 最近的请求次数 | Number of ...

    百度地图毕业设计源码-LeetCode:LeetCode习题集

    百度地图毕业设计源码 LeetCode(已转移) LeetCode习题集 第三课 Array 实战题目 LeetCode地址: 代码: ...moveZeroes(int[] nums) { int j = 0; for (int i = 0; i &lt; nums.length; i++) { i

    lrucacheleetcode-LeetCode:复制和思考

    Zeroes 数学分析 递归和循环 20200525 191. Number of 1 Bits 二进制 二进制如何记录1的个数 20200526 287. Find the Duplicate Number 指针 快慢指针,链表循环 20200529 198. House Robber 动态规划 如何确定子问题...

    recommended-problems

    这是我准备面试时建议的个人问题清单。 图表 数组 散列 链表 ... ... https://leetcode.com/problems/set-matrix-zeroes/ 弦乐 https://leetcode.com/problems/positions-of-large-g

    lrucacheleetcode-LeetCode_30Day:力扣30天挑战赛

    lru缓存leetcode 力扣_30天 力扣 30 天挑战赛 日 问题描述 问题和解决方案链接 Git 解决方案页面 1 SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ...

Global site tag (gtag.js) - Google Analytics