面试经典150题——矩阵置零

这篇具有很好参考价值的文章主要介绍了面试经典150题——矩阵置零。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

​"Dream it. Wish it. Do it." - Unknown

面试经典150题——矩阵置零,算法,数据结构,leetcode

1. 题目描述

面试经典150题——矩阵置零,算法,数据结构,leetcode

2.  题目分析与解析

2.1 思路一——暴力求解

思路一很简单,就是尝试遍历矩阵的所有元素,如果发现值等于0,就把当前行与当前列的值分别置为0。同时我们需要注意,因为如果出现下图所示的情况:

面试经典150题——矩阵置零,算法,数据结构,leetcode

比如发现matrix[0][0]等于0,我们把第一列和第一行置为0,但是被置为0的行的最后一个元素如上红色框原本也为0,所以这一行与列也要置为0,如果我们单纯把当前行与列覆盖就不知道原来的位置是什么值。并且如果不使用额外空间,我们比如把某一行某一列都置为了0,那么我们在后续遍历时发现这一行这一列的所有元素都为0,都需要处理,那肯定是错误的。所以这就要求我们必须把原始矩阵存储起来。使用额外的O(MN)空间。

2.2 思路二——优化

因为题目中告诉我们仅需要把是matrix中值为0的所在行与所在列元素置为0,那么如果要减少额外的空间使用,我们是不是就可以先遍历matrix单独只存储为0的部分的行列值,然后再将这些为0的值的行列一个个设置为0?这样使用的额外空间就是根据矩阵中为0的元素的个数来计算的。

但是想象一下最坏的情况,如果所有矩阵元素都为0,那么我们是不是就需要M*N个行列,也就是 M*N*2的额外空间大小,那不是还没第一种方法用的额外空间小?

但是如果我们不存储行与列,而是存储当前行与列是否需要置为0的真假,可不可以?如果我们遇到某一个值为0,那么我们就将两个数组的对应第 i 和第二个数组的第 j 个位置置为true,表示我们 i 行,j 列需要置为0,那么即使后续遍历到了其它在当前行或者当前列的某一个值为0的元素,通过查看数组,肯定有一个值为true,只需要把它所单独在的行或者列对应数组的位置置为true就可以。

所以本质上这种方法就是采用两个数组,来表示哪一行需要置为0,哪一列需要置为0。然后再根据数组的真假,将对应行与列置为0。

这种方法会使用O(m + n) 的额外空间。

2.3 思路三——优化2

因为题目提示了

  • 你能想出一个仅使用常量空间的解决方案吗?

那说明肯定有更好的方案,所以我们再想一想。

抓住问题的本质,我们问题的本质不是找哪个元素的值为0,我们的本质是需要将值为0的行于列的元素置为0。并且以前都是空间换时间,现在想要减小空间,那么是不是可以用时间换空间?

根据我的理解,时间与空间实际上就是对于信息的存储形式,而信息总量不变,因此时间增大那么空间就肯定可以变小,时间减小那么额外的信息就需要使用空间来存储。(当然这要建立在完美的算法上,并且也仅仅是个人的理解)

因此我们是不是可以直接不存储那个元素为0,我们只需要一行行遍历矩阵,发现某个元素为0,记录下它所在的列,等到改行遍历完毕,回过头把该行置为0(如果改行有0元素)。在遍历后续行的时候,我们就可以根据前面发现值为0的列将对应位置直接置为0。

代码思路:

  1. 初始化一个数组,用来记录需要置为0的列

  2. 遍历矩阵的第一行,发现值为0的元素,就将列值加入数组(如果数组不包含该列的话),然后再将该行所有元素赋值为0

  3. 如果该行没有值为0的元素,就直接遍历下一行

  4. 最后遍历column数组,将matrix的第j列的所有元素置为0

这样使用的空间:使用 ArrayList 来存储需要置0的列索引:O(N),在最坏的情况下,如果矩阵的每一列都至少有一个0,则需要存储所有列的索引。

2.4 思路四——优化3

这是我看官方的解析,官方很巧妙的将矩阵的第一行与第一列当作判定数组。其实本质上就和前面的思路2一样,采用两个数组,来表示哪一行需要置为0,哪一列需要置为0,但是这两个数组是用的矩阵原始的第一行与第一列。我将代码加了注释,所以直接读代码应该很清晰:

  • 同时需要注意,有些人会问如果第一行或者第一列根本没有0,那你再用它当标志位,之前的值怎么办?

  • 所以我需要解释一下:之所以使用第一行与第一列无需再存储它之前的值是因为我们仅仅修改在发现当前行者当前列为0的地方,也就是其它位置我是不动的,如下:

面试经典150题——矩阵置零,算法,数据结构,leetcode

  • 当我发现蓝色位置为0,我只更改红色位置的值,这些位置即使第一行与第一列没有0,也是需要更改的。而在结束时如果根据两个判定变量发现第一行与第一列本来没有0,就不需要在做更改了,因为根本没有更改不需要更改的部分。

面试经典150题——矩阵置零,算法,数据结构,leetcode

面试经典150题——矩阵置零,算法,数据结构,leetcode

可以看出这种方法效率还是很高的。

2.5 思路五——优化4

按照上面的官方解析,那就再把思路三种的ArrayList放在矩阵第一行,那也可以使用更少的空间。说做就做,在看了思路三的基础上直接看下面的代码吧

面试经典150题——矩阵置零,算法,数据结构,leetcode

面试经典150题——矩阵置零,算法,数据结构,leetcode

2.6 思路六——优化5——只使用一个变量

在思路五的基础上,我们的判断当前行是否需要置为0的flag是可以省略掉的,如下:

面试经典150题——矩阵置零,算法,数据结构,leetcode

注意这一行:

将该行第一个元素当作一个标志位,判断是否需要将该行的元素置为0

(如果该行某个元素为0,那么将该行的所有元素应该置为0,因此无所谓用该行哪个元素当标志位都是可以的)

面试经典150题——矩阵置零,算法,数据结构,leetcode

按照这种思路只需要使用一个布尔变量就可以完成任务,还是很巧妙的。

3. 代码实现

3.1 思路一

面试经典150题——矩阵置零,算法,数据结构,leetcode

面试经典150题——矩阵置零,算法,数据结构,leetcode

3.2 思路二

面试经典150题——矩阵置零,算法,数据结构,leetcode

面试经典150题——矩阵置零,算法,数据结构,leetcode

3.3 思路三

面试经典150题——矩阵置零,算法,数据结构,leetcode

面试经典150题——矩阵置零,算法,数据结构,leetcode

思路四五六见上

4. 相关复杂度分析

1. 暴力求解

  • 时间复杂度: (O(M^2N + MN^2))。因为对于矩阵中的每一个元素,都可能需要遍历整行和整列来将它们置为0。

解释:

面试经典150题——矩阵置零,算法,数据结构,leetcode

  • 空间复杂度: (O(MN))。需要一个同样大小的矩阵来存储副本。

2. 优化

  • 时间复杂度: (O(MN))。首先遍历一遍矩阵来标记需要置0的行和列,然后根据这些标记来置0,每个步骤都是线性的。

  • 空间复杂度: (O(M + N))。使用两个额外的数组来记录需要置0的行和列。

3. 优化2

  • 时间复杂度: (O(MN^2))。最坏情况下,对于矩阵的每一个元素,都可能需要遍历整个列索引列表来检查是否已经记录了该列。

  • 空间复杂度: (O(N))。使用一个ArrayList来记录需要置0的列。

4. 优化3

  • 时间复杂度: (O(MN))。遍历整个矩阵两次,一次用于标记,一次用于实际置0操作。

  • 空间复杂度: (O(1))。利用矩阵的第一行和第一列来记录0的位置,除了两个额外的标志位以外不需要其他额外空间。

5. 优化4

  • 时间复杂度: (O(MN))。虽然有多次遍历,但每次遍历都是线性的,关键操作还是依赖于矩阵的总元素数量。

  • 空间复杂度: (O(1))。仅使用一个额外的标志位来记录第一行是否需要置0,直接在原矩阵上操作。

6. 优化5

  • 时间复杂度: (O(MN))。和前一种方法类似,遍历矩阵来标记0的位置,然后根据这些标记来置0。

  • 空间复杂度: (O(1))。使用矩阵的第一行和第一个元素来记录行和列是否需要置0,没有使用其他额外空间。

但显然,随着优化的进行,我们尽量减少了空间复杂度,直至达到常数空间复杂度的解法,同时保持了时间复杂度为线性。总之来说还是很有意思的。文章来源地址https://www.toymoban.com/news/detail-832832.html

到了这里,关于面试经典150题——矩阵置零的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年01月16日
    浏览(72)
  • Leetcod面试经典150题刷题记录 —— 矩阵篇

    Leetcod面试经典150题刷题记录-系列 Leetcod面试经典150题刷题记录——数组 / 字符串篇 Leetcod面试经典150题刷题记录 —— 双指针篇 本篇 Leetcod面试经典150题刷题记录 —— 矩阵篇 Leetcod面试经典150题刷题记录 —— 滑动窗口篇 Leetcod面试经典150题刷题记录 —— 哈希表篇 Leetcod面试

    2024年02月03日
    浏览(44)
  • 【leetcode刷题之路】面试经典150题(2)——双指针+滑动窗口+矩阵

    2 双指针 2.1 【双指针】验证回文串 题目地址:https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2envId=top-interview-150   详见代码。 2.2 【双指针】判断子序列 题目地址:https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2envId=top-interview-150   双指针挨个遍

    2024年02月19日
    浏览(50)
  • 【Elacticsearch】 原理/数据结构/面试经典问题整理

    对Elacticsearch 原理/数据结构/面试经典问题整理的文章; 映射 | Elasticsearch: 权威指南 | Elastic 目录 Elacticsearch介绍 原理 建立索引原理 查询索引原理 更新索引原理 删除索引原理 分片副本机制,集群发现选举机制 ,负载机制,容错机制,扩容机制 数据类型 数据结构 先介绍倒排

    2024年02月10日
    浏览(46)
  • 数据结构(五)数据结构与算法中的经典题

    本文是在原本数据结构与算法闯关的基础上总结得来,加入了自己的理解和部分习题讲解。至此数据结构介绍已完结,后续会把数据结构算法题系列更完。 原活动链接 邀请码: JL57F5 根据要求完成题目 Q1. (单选)以下哪些数据结构支持随机访问? A. 数组 B. 单链表 C. 双向链表

    2024年01月20日
    浏览(44)
  • 经典面试题:玩家进游戏场地分配号码、判断括号是否闭合、提取回文串字符的分析和 php 程序实现 - 经典数据结构面试

        给定一长串字母和符号,里面有三种括号包括([{}])这些,需要判断这三种括号必须是配对的。即这三类括号要么不出现,要出现必须是先出现左边的括号,然后出现右边的,中间括号可以嵌套。     定义一个字符对应关系数组,初始化一个数组栈。所以进入的左边符号入

    2024年04月25日
    浏览(43)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(65)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(75)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(83)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包