LeetCode 73，為什麼第一反應想到的解法很有可能是個坑？_網頁設計公司

今天是LeetCode第42篇文章，我們來看看LeetCode第73題矩陣置零，set matrix zeroes。

這題的難度是Medium，通過率在43%左右，從通過率上可以看出這題的難度並不大。但是這題的解法不少，從易到難，有很多種方法。而且解法和它的推導過程都挺有意思，我們一起來看下。

題意

首先我們來看題意，這題的題意很簡單，給定一個二維數組。要求我們對這個數組當中的元素做如下修改，如果數組的i行j列為0，那麼將同行和同列的元素全部置為0。要求我們直接在原數組上進行修改，而不是返回一個新的數組。

言下之意，要求我們實現一個in-place的方法，而避免額外開闢新的內存。

樣例

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

近在眼前的解法原來是坑

這題的題意非常簡單，解法也非常明顯，以至於很多人拿到它都會當做模擬題來解決。即遍歷一下數組，如果找到0，那麼將它所在的行和列賦值為0，然後繼續遍歷。

這段邏輯並不難寫，我們很容易寫出來：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """  Do not return anything, modify matrix in-place instead.  """
        n = len(matrix)
        if n == 0:
            return
        
        m = len(matrix[0])
        for i in range(n):
            for j in range(m):
                # 當我們找到為0的位置之後，將所在的行和列置為0
                if matrix[i][j] == 0:
                    for k in range(m):
                        matrix[i][k] = 0
                    for k in range(n):
                        matrix[k][j] = 0

但是很遺憾的是，這樣的做法是錯誤的，實際上連樣例都無法通過。通不過樣例的原因也很簡單， 因為0具有傳遞性。

舉個簡單的例子，假設第0行當中有一個0，那麼最後的結果一定是第0行全部被置為0。但問題是我們是在遍歷到0的時候來進行的set操作，這樣會將第0行的其他元素也置為0。這樣當我們遍歷到後面的位置之後，會繼續傳遞，從而將一些不該置為0的地方也置為0了。

舉個簡單的例子，比如：第0行是1 0 0 1。顯然由於第0行存在0，所以操作之後的結果一定是全為0。但問題是matrix[0][3]這個位置原本並不為0，但是如果我們在發現matrix[0][1]為0的時候，將它置為0的話，那麼當我們後面遍歷到matrix[0][3]得到0的時候，會無法判斷究竟是這個位置原本就是0，還是前面出現了0導致這一行全部變成了0。這兩者的操作是不同的。

眼看着目標就在眼前，好像一伸手就碰得到，但是偏偏好像這一步就是咫尺天涯，怎麼也碰不到。這種感覺想想都很難受，我想，當你試着用這種方法去解這道題然後發現不行的時候，一定會有這樣的感覺。並且你會發現好像也沒有什麼很好的辦法來優化。

這種情況在正式的算法比賽當中經常遇到，所以專業的競賽选手有了經驗（吃過虧）之後，想出思路的第一時間就會立即轉向思考，這樣做是不是會有什麼坑，或者是考慮不到的情況。嚴謹一點的同學還會構思幾組不同的測試數據進行測試，或者是腦海中模擬算法的運算。

剛不過去只能繞

以前我年輕的時候總是不信邪，有時候明知道這個方法並不好，或者是存在反例，但是仍會堅持想要通過自己的努力想出一個方案來解決它，而不是更換方法。

我不知道有多少人有同樣的想法，但是一般來說頭鐵的毛病最後總是會被治好的。這題算是一個不錯的例子，如果你堅持使用模擬的方法來做這道題，只有一種方案就是再創建一個同樣大小的數組來作為緩存。當我們遇到0的時候，我們不直接修改原數組中的結果，而是修改緩存，將同行和同列緩存數組中的元素置為0，最後再將緩存數組與原數組合併。

但是顯然這不是一種好的方法，因為題目要求in-place的目的就是為了節約空間，我們另外創建了一個同樣大小的數組顯然違背了題目的本意。

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

當全世界的人們隨著網路時代而改變向上時您還停留在『網站美醜不重要』的舊有思維嗎？機會是留給努力改變現況的人們，別再浪費一分一秒可以接觸商機的寶貴時間！

所以頭鐵到最後還是得認清現狀，這個方法不適合這道題，需要更換解法。如果是在比賽當中得出的這個結論，那麼很有可能獎牌已經和你沒什麼關係了。堅持和固執本身也許沒有太大的區別， 可能只是出現的場景不一樣。

進階解法

回到這道題本身，我們已經證明了模擬的思路是行不通的，除了一邊遍歷一邊操作可能帶來的混亂之外，還有一個點是這樣的複雜度很高。因為如果原數據當中如果本身0就很多的話，那麼我們會需要不停地操作，極端情況下，如果所有元素都是0，那麼我們每一個位置都需要操作一下行列，整體的複雜度會達到。

既然如此，還有什麼好的辦法嗎？

當然是有的，其實也挺明顯的，因為對於一個出現的0來說它會影響的範圍是固定的，就是所在的行和列，那我們是不是記錄下會全部置為0的行和列，最後再遍歷一遍數據，看下當前元素是不是出在置為0的範圍當中就可以了。這種方法需要我們再創建兩個數組，用來存儲行和列是否被置為0。

這個解法也很直觀，想到了代碼應該不難寫：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """  Do not return anything, modify matrix in-place instead.  """
        n = len(matrix)
        if n == 0:
            return
        
        m = len(matrix[0])
        rows = [0 for _ in range(n)]
        cols = [0 for _ in range(m)]
        
        # 記錄置為0的行和列
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 0:
                    rows[i], cols[j] = 1, 1
                    
        # 如果所在行或者列置為0，那麼當前位置為0
        for i in range(n):
            for j in range(m):
                if rows[i] or cols[j]:
                    matrix[i][j] = 0
                    

終極解法

上面的做法雖然通過之後的戰績不太光彩，沒能戰勝90%以上的提交，但是能夠通過，而且算法沒有數量級的差距，也算是可以的。如果讓我來做，我可能就想到這種方法為止了。但是題目當中明確說了，還有空間複雜度為O(1)的算法，逼得我進一步思考了一下。

一般來說我們都是優化時間複雜度，很少會優化空間複雜度。相比於優化時間，優化空間有時候更加困難。因為有些時候我們可以空間換時間，可以預處理，可以離線計算……方法相對比較多。但優化空間的方法則很少，尤其是很多時候還不能犧牲時間，所以一般來說只能從算法本身來優化，很少有什麼套路可以套用。

在這個問題當中，要優化空間複雜度到常數級，那麼說明我們連數組都不能用。也就是說不能記錄行和列的信息，但是我們也不能用模擬的方法來進行，那麼應該怎麼辦呢？

干想是很難想出來的， 但是我們換個思路，問題就完全不一樣了。上面的算法時間複雜度是最優的，空間複雜度不太行，那麼有沒有辦法既使用同樣的算法，又能節省空間呢？看起來似乎不可能，但是其實可以，方法說穿了也並不值錢，就是將數據想辦法存在已有的地方，而不是另外開闢空間。在這個問題當中，已有的地方當然就只有一個就是原數組。也就是說我們要把每一行和列是否為0的信息記錄在原數組當中，比如我們可以把第0行和第0列用來做這個事情。

但這樣又會帶來另外一個問題，如果第0行和第0列本身當中也有0出現該怎麼辦？沒辦法，只能特判了。我們單獨用變量來記錄第0行和第0列是否被置為0，這樣我們就最大化地利用了空間，將空間複雜度降低到了常數級。

代碼邏輯和上面一脈相承，只是多了一點騷操作。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """  Do not return anything, modify matrix in-place instead.  """
        n = len(matrix)
        if n == 0:
            return
        
        m = len(matrix[0])
        
        row, col = False, False
        
        # 特判0，0的位置
        if matrix[0][0] == 0:
            row, col = True, True
        
        # 特判第0列是否含0
        for i in range(n):
            if matrix[i][0] == 0:
                col = True
                break
                
        # 特判第0行是否含0
        for i in range(m):
            if matrix[0][i] == 0:
                row = True
                break
                
        # 將i行，j列是否為0的信息存入matrix當中
        for i in range(0, n):
            for j in range(0, m):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                    
        for i in range(1, n):
            for j in range(1, m):
                # 根據第0行與第0列數據還原
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
                  
        # 最後處理第0行與第0列
        if row:
            for i in range(m):
                matrix[0][i] = 0
                
        if col:
            for i in range(n):
                matrix[i][0] = 0

總結

到這裏，這道題就算是分享完了，它的題意簡單，但是解法挺多的，我個人感覺也許還存在更好的解法也不一定。

我個人做完這題最大的感受不是這題的思路如何，也不是它涉及的算法如何，而是想到了很多和算法題無關的事情。比如我們生活當中有沒有這樣看似簡單，但是做起來發現一點也不簡單的事情？有沒有眼看着目標就在眼前，卻發現選擇的路一開始就是錯的呢？

帶着這樣的思路來做題，會發現題目也變得有意思多了。

今天的內容就是這些，如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。