扯閑篇

為啥寫(xiě)這個(gè)題？ 因?yàn)檫@題由簡(jiǎn)單到難坑真是多。值得記錄下來(lái)好好研究研究

題目

Given a?mxn?matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?

A straight forward solution using O(mn) space is probably a bad idea.

A simple improvement uses O(m+n) space, but still not the best solution.

Could you devise a constant space solution?

分析

首先 O(mn) 咋解？

這太簡(jiǎn)單了，你就復(fù)制一個(gè)矩陣 然后所有的 0 在復(fù)制的矩陣?yán)锩孀鼍涂梢粤恕?/p>

然后O(m+n) 咋解？?

你想啊，不是O(mn)里面要復(fù)制矩陣嘛，但是我們分析一下就知道，我們不需要知道矩陣?yán)锩恳粋€(gè)元素是什么，我們需要知道的是每一行每一列要不要設(shè)置成0 對(duì)吧？有思路了沒(méi)？

所以就每一行存一個(gè)變量O(m)，每一列存一個(gè)變量O(n)，?

第一次遍歷， 當(dāng)發(fā)現(xiàn)matrix[i][j] == 0的時(shí)候，行i標(biāo)記 列j標(biāo)記。

第二次遍歷，當(dāng)發(fā)現(xiàn)行i標(biāo)記了，matrix[i][0->n]= 0；發(fā)現(xiàn)列j標(biāo)記了，matrix[0->m][j] = 0 ；

結(jié)束

最后O(1)咋解？

好了問(wèn)題就來(lái)了，我們?cè)趺聪氤鰜?lái)這道題O(1)還能做呢？

因?yàn)槲覀冎鞍l(fā)現(xiàn)第一次進(jìn)化的時(shí)候有一個(gè)規(guī)律，就是我們需要用一個(gè)“什么東西”來(lái)保存行列是否標(biāo)零這個(gè)狀態(tài)。保存狀態(tài)的這個(gè)變量本身是不能改變的。所以我們要用一個(gè)常數(shù)空間來(lái)保存這個(gè)狀態(tài)，怎么辦呢？

直接想沒(méi)轍，改動(dòng)一下呢？我需要把所有的狀態(tài)都另開(kāi)一個(gè)變量存下來(lái)還是可以用矩陣本身存一點(diǎn)，另開(kāi)變量存一點(diǎn)呢？

看到這里肯定比我聰明的看官都知道要怎么做了。我們可以把[1->m][1->n]的狀態(tài)用第一行和第一列來(lái)保存，為了避免覆寫(xiě)第一行和第一列，第一行和第一列的狀態(tài)單獨(dú)保存，這就是我們要的答案。代碼附上

代碼自己點(diǎn)開(kāi)看哈~~? ?這也是為了讓大家看完了先想一想，像我一樣上來(lái)就抄一定會(huì)抄錯(cuò)的

哪里容易錯(cuò)

1. 不容易想到最優(yōu)解，或者看答案沒(méi)看明白（汗。。）覆寫(xiě)了第一行和第一列，導(dǎo)致的結(jié)果是全部清零。

2. 在最后寫(xiě)第一行第一列的時(shí)候行列顛倒了，導(dǎo)致的結(jié)果的該清零的地方?jīng)]有清零。