重庆市建设工程造价站,做的网站图片不显示,七牛云存储 wordpress 缩略图,深圳做网站哪家好Dream it. Wish it. Do it. - Unknown 1. 题目描述 2. 题目分析与解析
2.1 思路一——暴力求解
思路一很简单#xff0c;就是尝试遍历矩阵的所有元素#xff0c;如果发现值等于0#xff0c;就把当前行与当前列的值分别置为0。同时我们需要注意#xff0c;…Dream it. Wish it. Do it. - Unknown 1. 题目描述 2. 题目分析与解析
2.1 思路一——暴力求解
思路一很简单就是尝试遍历矩阵的所有元素如果发现值等于0就把当前行与当前列的值分别置为0。同时我们需要注意因为如果出现下图所示的情况 比如发现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。
代码思路 初始化一个数组用来记录需要置为0的列 遍历矩阵的第一行发现值为0的元素就将列值加入数组如果数组不包含该列的话然后再将该行所有元素赋值为0 如果该行没有值为0的元素就直接遍历下一行 最后遍历column数组将matrix的第j列的所有元素置为0
这样使用的空间使用 ArrayList 来存储需要置0的列索引O(N)在最坏的情况下如果矩阵的每一列都至少有一个0则需要存储所有列的索引。
2.4 思路四——优化3
这是我看官方的解析官方很巧妙的将矩阵的第一行与第一列当作判定数组。其实本质上就和前面的思路2一样采用两个数组来表示哪一行需要置为0哪一列需要置为0但是这两个数组是用的矩阵原始的第一行与第一列。我将代码加了注释所以直接读代码应该很清晰 同时需要注意有些人会问如果第一行或者第一列根本没有0那你再用它当标志位之前的值怎么办 所以我需要解释一下之所以使用第一行与第一列无需再存储它之前的值是因为我们仅仅修改在发现当前行者当前列为0的地方也就是其它位置我是不动的如下 当我发现蓝色位置为0我只更改红色位置的值这些位置即使第一行与第一列没有0也是需要更改的。而在结束时如果根据两个判定变量发现第一行与第一列本来没有0就不需要在做更改了因为根本没有更改不需要更改的部分。 可以看出这种方法效率还是很高的。
2.5 思路五——优化4
按照上面的官方解析那就再把思路三种的ArrayList放在矩阵第一行那也可以使用更少的空间。说做就做在看了思路三的基础上直接看下面的代码吧 2.6 思路六——优化5——只使用一个变量
在思路五的基础上我们的判断当前行是否需要置为0的flag是可以省略掉的如下 注意这一行 将该行第一个元素当作一个标志位,判断是否需要将该行的元素置为0 (如果该行某个元素为0,那么将该行的所有元素应该置为0,因此无所谓用该行哪个元素当标志位都是可以的) 按照这种思路只需要使用一个布尔变量就可以完成任务还是很巧妙的。
3. 代码实现
3.1 思路一 3.2 思路二 3.3 思路三 思路四五六见上
4. 相关复杂度分析
1. 暴力求解 时间复杂度: (O(M^2N MN^2))。因为对于矩阵中的每一个元素都可能需要遍历整行和整列来将它们置为0。 解释 空间复杂度: (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没有使用其他额外空间。
但显然随着优化的进行我们尽量减少了空间复杂度直至达到常数空间复杂度的解法同时保持了时间复杂度为线性。总之来说还是很有意思的。
