這個題乍一看很簡單,實際上還挺有技巧的。我最開始的想法是找一個特殊值標記,遇到一個0,把他所對應的行列中非零的元素標記成這個特殊值,0值保持不變,然後再從頭遍歷一次,碰到特殊值就轉化成0。
問題是這個特殊值怎麼確定,題目中沒有把取值范圍給出,我懷著僥幸的心理用了最大和最小的int,都被揪了出來。。如果找一個不存在於數組中的值,這個復雜度太高了。
有沒有其他更好的方法呢?當然有。這個思想很巧妙,最後的結果是把所有0所在的行列都化成0,換句話說,化成0這個事情只要標記出是哪一行以及哪一列就可以了,能不能找到一種標記的方式來完成這個事情呢?做法是如果掃描到一個0,我們就把這個數的行列第一個數值置成0,用來做標記位,等全部掃描完畢後,針對為第一行和第一列為0的那些行列,置成0就可以了。
有一個細節,第一行和第一列該怎麼辦,他們可能一開始並沒有0,因為標記的原因有0了,怎麼區分呢?處理方式其實很簡單,一開始先看一下它含不含0,然後在最後根據這個結果來決定要不要把他們變成0.
class Solution { public: void setZeroes(vector> &matrix) { int row = matrix.size(), column = matrix[0].size(); bool firstRow = false, firstColumn = false; for(int i=0;i |