寫零問題詳解：雙指針與邊界條件全解析)
“復(fù)寫零”這道題我在很多次筆試和模擬面試?yán)镆娺^它。題目描述短到一眼就能看完給定一個固定長度的整數(shù)數(shù)組遇到0就把它復(fù)寫一份其余元素全部右移超過數(shù)組長度的部分直接截掉而且必須原地修改。很多人看到之后覺得“這不就是個模擬嗎”結(jié)果一動手就翻車新建數(shù)組的人違反空間限制用插入法的人寫出了O(n2)原地正序遍歷的人把還沒處理的元素覆蓋了。真正讓這道題從“會寫”變成“寫對”的是雙指針里那個“從后往前”的直覺和一層很容易被忽略的邊界條件。這篇就把這個題完整拆開講清楚兩趟掃描的原理、邊界特判到底在防什么以及同類的雙指針題怎么舉一反三。1. 先看懂題目復(fù)寫零到底在干什么1.1 題面與示例題目本身不長翻譯成人話是這樣的給你一個長度固定的數(shù)組你把每一個0都變成兩個0其他數(shù)字不變順序也不變整體向右擠壓凡是超出原數(shù)組長度的元素全部丟棄。關(guān)鍵約束是“原地修改”也就是不能另外開一個等長的數(shù)組來承接結(jié)果。舉一個最典型的例子輸入[1, 0, 2, 3, 0, 4, 5, 0]輸出[1, 0, 0, 2, 3, 0, 0, 4]。我們拆開看邏輯展開的過程1 變成 1第一個 0 變成 0, 02 變成 23 變成 3第二個 0 變成 0, 04 變成 45 變成 5最后一個 0 變成 0, 0邏輯上完整的新序列是[1, 0, 0, 2, 3, 0, 0, 4, 5, 0, 0]長度已經(jīng)變成11而原數(shù)組長度是8所以最后三個格子5, 0, 0直接被丟棄最終數(shù)組就是[1, 0, 0, 2, 3, 0, 0, 4]。沒有0的情況也順一遍[1, 2, 3]復(fù)寫后還是[1, 2, 3]因為沒有一個元素發(fā)生翻倍。這道題本身邏輯不復(fù)雜但它的陷阱正好藏在“原地”和“截斷”這兩個詞上。1.2 為什么最直覺的解法反而不行正常人第一次看到這個題腦子里冒出來的多半是“那我重新建一個數(shù)組遍歷原數(shù)組遇到0寫兩遍遇到非0寫一遍最后截取前n個完事”。這個做法結(jié)果完全正確時間也是O(n)但它開辟了額外空間空間復(fù)雜度是O(n)。題目里“原地修改”這四個字直接堵死了這條路。換個思路有人會想“我直接在原數(shù)組里插入0”。以 Python 的list.insert為例每一次在位置i插入0都需要把i后面的元素整體后移一位這一步就是O(n)的。如果數(shù)組里有m個0總體復(fù)雜度逼近O(n*m)在0密度高的數(shù)據(jù)上就是O(n2)比如全0數(shù)組會卡到懷疑人生。C里用vector::insert同理。所以這道題表面上考“數(shù)組模擬”實際考的是能不能在O(1)額外空間里完成擴容式的拷貝。一旦意識到這個約束雙指針幾乎是注定要走的路。1.3 用“整理書架”理解原地擴容為什么從前往后會出事從后往前就不會可以想象一排書架上擺了8本書現(xiàn)在要求把其中所有的“0書”都變成兩本其余書保持相對順序最終還是只擺8本。如果你從左往右整理當(dāng)你把第3本書復(fù)制成兩本、往右塞的時候第4本書的位置會被占掉。你還沒處理它呢它的原內(nèi)容就被覆蓋了。等你讀到那個位置時原書已經(jīng)沒了。如果反過來從書架最右邊開始整理每次把一本書放到它最終該在的位置左邊那些還沒移動的書完全不受影響。因為你動的是右邊已經(jīng)處理完的區(qū)域永遠(yuǎn)碰不到左邊還沒讀的書。這就是這道題最核心的操作直覺目標(biāo)數(shù)組比原數(shù)組長原地操作時優(yōu)先從后往前寫。2. 雙指針切入第一趟找邊界第二趟倒著寫2.1 雙指針在這里不是快慢而是“讀指針”和“寫指針”說到雙指針很多人第一時間想到鏈表里的快慢指針或者二分查找里的左右夾逼。但數(shù)組原地修改類的題目里更常用的雙指針模型其實是“讀指針”和“寫指針”一個指針負(fù)責(zé)遍歷原始數(shù)據(jù)另一個指針負(fù)責(zé)往結(jié)果位置寫入。復(fù)寫0這個題里讀指針和寫指針的關(guān)系有點特殊因為數(shù)組要變長寫指針的移動速度會比讀指針快。遇到一個0時讀指針往前走一格寫指針卻要往前走兩格。正因為兩個指針不同速才導(dǎo)致直接用一趟從頭到尾的遍歷無法完成——寫指針會超過讀指針覆蓋掉還沒讀取的數(shù)據(jù)。解決辦法很樸素既然從頭到尾會越讀越亂那就從尾到頭?？蓡栴}又來了從尾到頭寫的時候?qū)懼羔樢婚_始應(yīng)該落在哪個位置直接落在n-1對嗎不對因為邏輯上數(shù)組擴容后的尾部并不是原數(shù)組的尾部。必須先知道擴容后哪些元素會被截斷。于是就有了經(jīng)典的兩趟結(jié)構(gòu)。2.2 第一趟掃描“虛擬擴容后”的數(shù)組確定有效前綴我們可以想象數(shù)組擴容后的樣子雖然實際不能開新數(shù)組但邏輯上可以算出來。設(shè)n len(arr)zeros記錄掃描到當(dāng)前位置為止復(fù)寫0帶來的額外空間占用。每遇到一個非0元素它在擴展后序列里占1個位置每遇到一個0它在擴展后序列里占2個位置。第一趟掃描的循環(huán)條件寫成while i zeros n這個條件的意思是當(dāng)前這個原始元素如果寫進擴容后的數(shù)組它的最后一個位置是否還能落在原數(shù)組長度之內(nèi)如果能說明它活著如果i zeros已經(jīng)到邊界甚至超過邊界說明它以及它后面的所有元素都會在截斷中消失。以[1, 0, 2, 3, 0, 4, 5, 0]為例我做一個完整追蹤表步驟iarr[i]進入前 zerosi zeros是否滿足 n8操作后 zeros10100是保留021001是保留132213是保留143314是保留154015是保留265427是保留276528否退出2循環(huán)退出時i 6說明索引6和7的元素都會被截斷有效前綴是索引0到5這一段。把i--之后i 5就是最后一個存活的原始元素下標(biāo)。這一步的本質(zhì)是用虛擬下標(biāo)去卡邊界找出哪些原始數(shù)據(jù)能活到最終數(shù)組里。2.3 第二趟從有效前綴末尾開始倒著復(fù)寫當(dāng)?shù)谝惶舜_定了最后一個存活的原始元素的坐標(biāo)之后第二趟就很直接了。初始化寫指針write n - 1也就是最終數(shù)組真正的尾部。讀指針read從第一趟算出的有效前綴末尾開始。每一輪循環(huán)做這樣的事如果arr[read]是0就往arr[write]和arr[write - 1]各寫入一個0寫指針前進兩格如果arr[read]不是0就把原值寫到arr[write]寫指針前進一格讀指針每次前進一格。因為讀指針從有效前綴的末尾出發(fā)寫指針從數(shù)組末尾出發(fā)而有效前綴的末尾一定不晚于數(shù)組末尾所以寫指針始終在右側(cè)就算連續(xù)寫兩個0寫指針左移兩格也不太可能越過讀指針。即使某個極端情形下寫指針短暫到達讀指針附近讀指針此時已經(jīng)不會再需要那些位置上的原始數(shù)據(jù)了。整個遍歷過程天然避免了覆蓋未讀數(shù)據(jù)。還是[1, 0, 2, 3, 0, 4, 5, 0]第一趟結(jié)束后zeros 2有效前綴末尾是索引5。第二趟從read 5write 7開始倒著寫一圈就能得到[1, 0, 0, 2, 3, 0, 0, 4]。3. 完整解題方案與多語言實現(xiàn)3.1 分步驟拆解算法流程整個算法整理成三步第一趟統(tǒng)計用zeros記錄復(fù)寫0帶來的額外占用循環(huán)條件卡住數(shù)組邊界找出有效前綴的末尾位置。邊界特判如果最后一個存活元素正好是0且它只占據(jù)了數(shù)組的最后一格那么這個0只能復(fù)寫一次需要單獨處理。這是全題最容易出錯的地方。第二趟倒寫讀指針從有效前綴末尾向左走寫指針從數(shù)組末尾向左走根據(jù)當(dāng)前元素是否為0決定寫一格還是寫兩格。3.2 邊界特判到底在防什么很多人的代碼死在這一步。看一個具體例子輸入[1, 0, 0, 2]第一趟掃描后zeros 2i最終指向索引2。這里i zeros 2 2 4恰好等于n 4。這說明最后一個存活元素是索引2的0但它在邏輯展開后占兩個位置而數(shù)組只剩末尾一個空位了。也就是說這個0只能寫一次到arr[3]第二個0要被截斷。如果不在第二趟開始前把這個事處理掉倒寫時讀指針讀到索引2的0會往arr[3]和arr[2]連寫兩個0結(jié)果把數(shù)組搞得面目全非。正確的特判是if zeros 0 and i zeros n: arr[n - 1] 0 write - 1 read - 1先把能寫的那一個0放到數(shù)組末尾同時寫指針和讀指針各前移一格。這樣索引2的0就被視為“已經(jīng)完成了單次復(fù)制”不會再進入第二趟循環(huán)。推演一遍特判后 read 指向索引1write 指向索引2讀到索引1的0往arr[2]和arr[1]寫0讀到索引0的1往arr[0]寫1最終數(shù)組是[1, 0, 0, 0]和人工推演完全一致。3.3 Python 實現(xiàn)def duplicateZeros(arr): n len(arr) zeros 0 i 0 # 第一趟找出有效前綴邊界 while i zeros n: if arr[i] 0: zeros 1 i 1 # i 此時指向第一個不可能存活的位置減1得到有效前綴末尾 i - 1 write n - 1 # 邊界特判最后一個有效元素是0且只能寫一次 if zeros 0 and i zeros n: arr[write] 0 write - 1 i - 1 # 第二趟從后往前倒寫 while write 0: if arr[i] 0: arr[write] 0 write - 1 arr[write] 0 write - 1 else: arr[write] arr[i] write - 1 i - 1這段代碼里最值得注意的兩個地方第二趟的循環(huán)條件用write 0而不是i 0可以防止讀指針越界邊界特判里寫指針和讀指針都要同步前移。3.4 C 與 Java 實現(xiàn)C版本void duplicateZeros(vectorint arr) { int n arr.size(); int zeros 0; int i 0; while (i zeros n) { if (arr[i] 0) zeros; i; } i--; int write n - 1; if (zeros 0 i zeros n) { arr[write] 0; write--; i--; } while (write 0) { if (arr[i] 0) { arr[write] 0; write--; arr[write] 0; write--; } else { arr[write] arr[i]; write--; } i--; } }Java版本public void duplicateZeros(int[] arr) { int n arr.length; int zeros 0; int i 0; while (i zeros n) { if (arr[i] 0) zeros; i; } i--; int write n - 1; if (zeros 0 i zeros n) { arr[write] 0; write--; i--; } while (write 0) { if (arr[i] 0) { arr[write--] 0; arr[write--] 0; } else { arr[write--] arr[i]; } i--; } }三種語言的核心邏輯完全一致只是語法細(xì)節(jié)不同。Java里連續(xù)兩次write--簡寫在一行里注意別把指針移動次序搞反就行。3.5 復(fù)雜度分析第一趟循環(huán)最多掃描到n個元素就停第二趟倒寫也只需要處理有效前綴長度范圍內(nèi)的元素。兩趟加起來是嚴(yán)格O(n)即使是全0數(shù)組第一趟也會因為i zeros n快速退出。空間方面只用了zeros、i、write三個整數(shù)變量沒有開辟任何數(shù)組空間復(fù)雜度O(1)。時間上可能有人會問第二趟循環(huán)里遇到0會連寫兩次會不會多一次操作不會因為寫入這兩個0正好對應(yīng)它復(fù)寫后的兩個格子寫入次數(shù)和最終數(shù)組長度是一一對應(yīng)的。總體操作次數(shù)仍然和數(shù)組長度成正比。4. 最容易翻車的邊界條件4.1 末尾是0復(fù)寫一次還是兩次這是整道題最大的坑單獨拿出來說。判斷邏輯是如果最后一個“存活”的原始元素剛好是0而且它復(fù)寫后占兩個格子但數(shù)組只剩一個空位那么這個0只能復(fù)寫一次。寫成代碼就是i zeros n這個條件。我用四個例子做個速查表輸入邏輯展開后前n位代碼結(jié)果說明[1, 0, 0, 2][1, 0, 0, 0][1, 0, 0, 0]最后一個存活元素0只寫一次[0, 0, 1][0, 0, 0][0, 0, 0]邊界0占據(jù)最后格子[0, 0, 0][0, 0, 0][0, 0, 0]前兩個0占4格只剩3格[0, 1, 0][0, 0, 1][0, 0, 1]第二個0直接被截斷這幾個用例看著差不多但如果不做邊界特判反應(yīng)在結(jié)果上就是末尾多了一個0或中間少了一個0。4.2 空數(shù)組和單元素數(shù)組空數(shù)組就不說了什么循環(huán)都不會進入直接返回。單元素數(shù)組要看元素是不是0[0]復(fù)寫后邏輯上是[0, 0]截斷成[0]。第一趟掃描時i zeros 1i0時遇到0zeros變成1i變成1退出i1減到0i zeros 1 n觸發(fā)特判把arr[0] 0后 write變成-1read變成-1第二趟不執(zhí)行最終是[0]。[3]沒有0第一趟掃描后 zeros0不觸發(fā)特判第二趟把arr[0]原樣寫回最終[3]。這兩個小用例用來驗證代碼的健壯性特別好刷完題之后可以順手測一下。4.3 手工推演一個全0數(shù)組全0數(shù)組是很多人寫崩的場景。拿[0, 0, 0]來說邏輯上復(fù)寫后是6個0截斷成3個0看起來結(jié)果沒變化但代碼必須正確處理。第一趟掃描i0zeros0進入循環(huán)arr[0]0zeros變成1i變?yōu)?i1zeros11 1 3成立arr[1]0zeros變成2i變?yōu)?i2zeros22 2 3不成立退出退出后i 2減一變成1。此時i zeros 1 2 3 n觸發(fā)特判arr[2] 0write變成1i變成0。第二趟從 i0 開始讀到一個0寫兩格到arr[1]和arr[0]。最終仍然是三個0。如果不做特判第二趟從 i1 開始寫到后面就會發(fā)現(xiàn) write 已經(jīng)變負(fù)但讀指針還有元素沒處理或者最后多寫一個0導(dǎo)致數(shù)組被寫穿。運行時報錯還是小事靜默返回錯誤結(jié)果更可怕。4.4 常見錯誤速查表錯誤寫法錯誤后果正確做法第一趟循環(huán)用for i in range(n)多統(tǒng)計被截斷的0有效前綴偏移用while i zeros n卡邊界第二趟直接從read n - 1開始末尾原始數(shù)據(jù)可能被錯誤復(fù)制中間被覆蓋從有效前綴末尾開始邊界0不做特判數(shù)組末尾出現(xiàn)連續(xù)兩個0以外的錯位用i zeros n判斷并單寫一次第二趟條件寫成while i 0寫指針可能已經(jīng)出界但讀指針仍有殘留觸發(fā)越界用while write 0特判后只移動讀指針不移動寫指針邊界0被寫兩次后面數(shù)據(jù)錯位讀指針和寫指針都前移一格5. 一法通百法雙指針題的遷移思路5.1 三種雙指針模型數(shù)組題里的雙指針大致能分成三類快慢指針一個指針走得快一個走得慢常用于鏈表找環(huán)、數(shù)組去重。左右對撞指針一個從左邊走一個從右邊走常用于有序數(shù)組求和、反轉(zhuǎn)數(shù)組。讀寫指針一個負(fù)責(zé)讀原數(shù)組一個負(fù)責(zé)往結(jié)果位置寫常用于原地刪除、原地移動?！皬?fù)寫零”屬于第三種。這類題的核心判斷方式是如果目標(biāo)數(shù)組比原數(shù)組短一般從前往后用快慢指針如果目標(biāo)數(shù)組比原數(shù)組長基本要從后往前用讀寫指針。5.2 和“移動零”“原地去重”的對比原地去重這道題目標(biāo)數(shù)組比原數(shù)組短所以用一個慢指針指向“下一個不重復(fù)元素該放的位置”快指針從頭掃描原數(shù)組發(fā)現(xiàn)新元素就寫過去。這種從前往后沒問題因為快指針一定在慢指針前面或相等?！耙苿恿恪币彩峭粋€道理先把所有非零元素集中到前面再把后面全部補0。它不需要擴容所以從前往后寫完全安全。“復(fù)寫零”反過來目標(biāo)長度變長每一個0都要多占一個位置。此時從前往后寫寫指針會超過讀指針覆蓋未讀數(shù)據(jù)所以必須倒過來。合并兩個有序數(shù)組也是這個思路第一個數(shù)組尾部預(yù)留了足夠空間從后往前比較并寫入誰大誰先放根本不需要額外數(shù)組。總結(jié)成一句話目標(biāo)變長先找邊界再從后往前寫目標(biāo)變短快慢指針直接從前掃。5.3 面試?yán)镌趺纯焖僮R別這類題你看一個數(shù)組題如果要求原地修改先把最終長度和原始長度做比較。最終長度大于原始長度八成要用到“先擴容再倒寫”的思路最終長度小于或等于原始長度大概率是快慢指針的前向覆蓋?！皬?fù)寫零”表面上是模擬實際是“擴容式原地修改”的入門題。理解了它再去做“合并兩個有序數(shù)組”“字符串中的空格替換”這類題就會順暢很多因為它們共用同一套從后往前的直覺。6. 面試現(xiàn)場怎么在幾分鐘內(nèi)講清楚解法6.1 先給暴力解再談優(yōu)化面試遇到這題不用一上來就甩雙指針。先快速說一句“最直接的辦法是新開數(shù)組遇到0寫兩遍時間復(fù)雜度O(n)但空間O(n)不符合原地要求”。這能讓面試官知道你對復(fù)雜度有意識。然后說第二層“如果要在原地做就必須考慮覆蓋問題。數(shù)組要變長正序?qū)憰采w后續(xù)元素所以大概率倒序但倒序前必須知道哪些元素能活到最終數(shù)組里于是第一趟先數(shù)0、卡邊界?！?.2 把雙指針方案壓縮成三句話整個方案用三句話就能說清第一趟用i zeros n掃描找出有效前綴的末尾位置。如果末尾元素是0且它只夠?qū)懸淮螁为毺幚磉@個邊界0。第二趟從有效前綴末尾出發(fā)讀指針和寫指針一起向左移動遇0寫兩格遇非0寫一格?？谑鰰r強調(diào)“讀指針和寫指針不同速”“從后往前不會覆蓋未讀數(shù)據(jù)”“邊界0只寫一次”這三個點面試官基本就會點頭。6.3 我個人最推薦的代碼模板我在面試和平時刷題時習(xí)慣用的就是上面那套 Python 模板。它有幾個好處第一趟直接卡邊界不像某些寫法要先數(shù)完所有0再二次判斷邊界特判用i zeros n一目了然第二趟循環(huán)條件用write 0從根本上杜絕越界。def duplicateZeros(arr): n len(arr) zeros 0 i 0 while i zeros n: if arr[i] 0: zeros 1 i 1 i - 1 write n - 1 if zeros 0 and i zeros n: arr[write] 0 write - 1 i - 1 while write 0: if arr[i] 0: arr[write] 0 write - 1 arr[write] 0 write - 1 else: arr[write] arr[i] write - 1 i - 1這個模板可以直接背更重要的是每次寫完都手動跑一遍[1, 0, 0, 2]、[0, 0, 1]、[0, 0, 0]、[1, 0, 2, 3, 0, 4, 5, 0]這四個用例基本就能確認(rèn)邊界處理沒有問題。6.4 刷題建議與復(fù)盤心得這道題很適合放進“數(shù)組原地操作”專題里反復(fù)練習(xí)。第一次做建議先不看題解自己把正序的失敗過程推演一遍感受數(shù)據(jù)被覆蓋的瞬間第二次做再去看雙指針解法重點理解第一趟為什么能卡邊界第三次做可以把代碼默寫出來并主動給面試官講“如果最后一個有效元素是0會怎樣”。我自己帶人刷題時發(fā)現(xiàn)最容易卡住的地方不是雙指針本身而是那個邊界特判。很多人第一趟掃描寫對了但第二趟忘記處理“只夠?qū)懸淮蔚?”導(dǎo)致結(jié)果在末尾多出一個錯位。把[1, 0, 0, 2]這個用例刻進腦子里這個坑基本就不會再踩?！皬?fù)寫零”這類題還有一個隱藏價值它逼你跳出“從前往后”的思維慣性。實際開發(fā)里處理緩沖區(qū)擴容、日志滾動、歷史版本合并時從后往前寫都是一個很實用的技巧。刷題的價值有時候不在記住某個模板而在把這種“倒過來想”的直覺訓(xùn)練成本能。 復(fù)寫零問題詳解：雙指針與邊界條件全解析
“復(fù)寫零”這道題我在很多次筆試和模擬面試?yán)镆娺^它。題目描述短到一眼就能看完給定一個固定長度的整數(shù)數(shù)組遇到0就把它復(fù)寫一份其余元素全部右移超過數(shù)組長度的部分直接截掉而且必須原地修改。很多人看到之后覺得“這不就是個模擬嗎”結(jié)果一動手就翻車新建數(shù)組的人違反空間限制用插入法的人寫出了O(n2)原地正序遍歷的人把還沒處理的元素覆蓋了。真正讓這道題從“會寫”變成“寫對”的是雙指針里那個“從后往前”的直覺和一層很容易被忽略的邊界條件。這篇就把這個題完整拆開講清楚兩趟掃描的原理、邊界特判到底在防什么以及同類的雙指針題怎么舉一反三。1. 先看懂題目復(fù)寫零到底在干什么1.1 題面與示例題目本身不長翻譯成人話是這樣的給你一個長度固定的數(shù)組你把每一個0都變成兩個0其他數(shù)字不變順序也不變整體向右擠壓凡是超出原數(shù)組長度的元素全部丟棄。關(guān)鍵約束是“原地修改”也就是不能另外開一個等長的數(shù)組來承接結(jié)果。舉一個最典型的例子輸入[1, 0, 2, 3, 0, 4, 5, 0]輸出[1, 0, 0, 2, 3, 0, 0, 4]。我們拆開看邏輯展開的過程1 變成 1第一個 0 變成 0, 02 變成 23 變成 3第二個 0 變成 0, 04 變成 45 變成 5最后一個 0 變成 0, 0邏輯上完整的新序列是[1, 0, 0, 2, 3, 0, 0, 4, 5, 0, 0]長度已經(jīng)變成11而原數(shù)組長度是8所以最后三個格子5, 0, 0直接被丟棄最終數(shù)組就是[1, 0, 0, 2, 3, 0, 0, 4]。沒有0的情況也順一遍[1, 2, 3]復(fù)寫后還是[1, 2, 3]因為沒有一個元素發(fā)生翻倍。這道題本身邏輯不復(fù)雜但它的陷阱正好藏在“原地”和“截斷”這兩個詞上。1.2 為什么最直覺的解法反而不行正常人第一次看到這個題腦子里冒出來的多半是“那我重新建一個數(shù)組遍歷原數(shù)組遇到0寫兩遍遇到非0寫一遍最后截取前n個完事”。這個做法結(jié)果完全正確時間也是O(n)但它開辟了額外空間空間復(fù)雜度是O(n)。題目里“原地修改”這四個字直接堵死了這條路。換個思路有人會想“我直接在原數(shù)組里插入0”。以 Python 的list.insert為例每一次在位置i插入0都需要把i后面的元素整體后移一位這一步就是O(n)的。如果數(shù)組里有m個0總體復(fù)雜度逼近O(n*m)在0密度高的數(shù)據(jù)上就是O(n2)比如全0數(shù)組會卡到懷疑人生。C里用vector::insert同理。所以這道題表面上考“數(shù)組模擬”實際考的是能不能在O(1)額外空間里完成擴容式的拷貝。一旦意識到這個約束雙指針幾乎是注定要走的路。1.3 用“整理書架”理解原地擴容為什么從前往后會出事從后往前就不會可以想象一排書架上擺了8本書現(xiàn)在要求把其中所有的“0書”都變成兩本其余書保持相對順序最終還是只擺8本。如果你從左往右整理當(dāng)你把第3本書復(fù)制成兩本、往右塞的時候第4本書的位置會被占掉。你還沒處理它呢它的原內(nèi)容就被覆蓋了。等你讀到那個位置時原書已經(jīng)沒了。如果反過來從書架最右邊開始整理每次把一本書放到它最終該在的位置左邊那些還沒移動的書完全不受影響。因為你動的是右邊已經(jīng)處理完的區(qū)域永遠(yuǎn)碰不到左邊還沒讀的書。這就是這道題最核心的操作直覺目標(biāo)數(shù)組比原數(shù)組長原地操作時優(yōu)先從后往前寫。2. 雙指針切入第一趟找邊界第二趟倒著寫2.1 雙指針在這里不是快慢而是“讀指針”和“寫指針”說到雙指針很多人第一時間想到鏈表里的快慢指針或者二分查找里的左右夾逼。但數(shù)組原地修改類的題目里更常用的雙指針模型其實是“讀指針”和“寫指針”一個指針負(fù)責(zé)遍歷原始數(shù)據(jù)另一個指針負(fù)責(zé)往結(jié)果位置寫入。復(fù)寫0這個題里讀指針和寫指針的關(guān)系有點特殊因為數(shù)組要變長寫指針的移動速度會比讀指針快。遇到一個0時讀指針往前走一格寫指針卻要往前走兩格。正因為兩個指針不同速才導(dǎo)致直接用一趟從頭到尾的遍歷無法完成——寫指針會超過讀指針覆蓋掉還沒讀取的數(shù)據(jù)。解決辦法很樸素既然從頭到尾會越讀越亂那就從尾到頭?？蓡栴}又來了從尾到頭寫的時候?qū)懼羔樢婚_始應(yīng)該落在哪個位置直接落在n-1對嗎不對因為邏輯上數(shù)組擴容后的尾部并不是原數(shù)組的尾部。必須先知道擴容后哪些元素會被截斷。于是就有了經(jīng)典的兩趟結(jié)構(gòu)。2.2 第一趟掃描“虛擬擴容后”的數(shù)組確定有效前綴我們可以想象數(shù)組擴容后的樣子雖然實際不能開新數(shù)組但邏輯上可以算出來。設(shè)n len(arr)zeros記錄掃描到當(dāng)前位置為止復(fù)寫0帶來的額外空間占用。每遇到一個非0元素它在擴展后序列里占1個位置每遇到一個0它在擴展后序列里占2個位置。第一趟掃描的循環(huán)條件寫成while i zeros n這個條件的意思是當(dāng)前這個原始元素如果寫進擴容后的數(shù)組它的最后一個位置是否還能落在原數(shù)組長度之內(nèi)如果能說明它活著如果i zeros已經(jīng)到邊界甚至超過邊界說明它以及它后面的所有元素都會在截斷中消失。以[1, 0, 2, 3, 0, 4, 5, 0]為例我做一個完整追蹤表步驟iarr[i]進入前 zerosi zeros是否滿足 n8操作后 zeros10100是保留021001是保留132213是保留143314是保留154015是保留265427是保留276528否退出2循環(huán)退出時i 6說明索引6和7的元素都會被截斷有效前綴是索引0到5這一段。把i--之后i 5就是最后一個存活的原始元素下標(biāo)。這一步的本質(zhì)是用虛擬下標(biāo)去卡邊界找出哪些原始數(shù)據(jù)能活到最終數(shù)組里。2.3 第二趟從有效前綴末尾開始倒著復(fù)寫當(dāng)?shù)谝惶舜_定了最后一個存活的原始元素的坐標(biāo)之后第二趟就很直接了。初始化寫指針write n - 1也就是最終數(shù)組真正的尾部。讀指針read從第一趟算出的有效前綴末尾開始。每一輪循環(huán)做這樣的事如果arr[read]是0就往arr[write]和arr[write - 1]各寫入一個0寫指針前進兩格如果arr[read]不是0就把原值寫到arr[write]寫指針前進一格讀指針每次前進一格。因為讀指針從有效前綴的末尾出發(fā)寫指針從數(shù)組末尾出發(fā)而有效前綴的末尾一定不晚于數(shù)組末尾所以寫指針始終在右側(cè)就算連續(xù)寫兩個0寫指針左移兩格也不太可能越過讀指針。即使某個極端情形下寫指針短暫到達讀指針附近讀指針此時已經(jīng)不會再需要那些位置上的原始數(shù)據(jù)了。整個遍歷過程天然避免了覆蓋未讀數(shù)據(jù)。還是[1, 0, 2, 3, 0, 4, 5, 0]第一趟結(jié)束后zeros 2有效前綴末尾是索引5。第二趟從read 5write 7開始倒著寫一圈就能得到[1, 0, 0, 2, 3, 0, 0, 4]。3. 完整解題方案與多語言實現(xiàn)3.1 分步驟拆解算法流程整個算法整理成三步第一趟統(tǒng)計用zeros記錄復(fù)寫0帶來的額外占用循環(huán)條件卡住數(shù)組邊界找出有效前綴的末尾位置。邊界特判如果最后一個存活元素正好是0且它只占據(jù)了數(shù)組的最后一格那么這個0只能復(fù)寫一次需要單獨處理。這是全題最容易出錯的地方。第二趟倒寫讀指針從有效前綴末尾向左走寫指針從數(shù)組末尾向左走根據(jù)當(dāng)前元素是否為0決定寫一格還是寫兩格。3.2 邊界特判到底在防什么很多人的代碼死在這一步。看一個具體例子輸入[1, 0, 0, 2]第一趟掃描后zeros 2i最終指向索引2。這里i zeros 2 2 4恰好等于n 4。這說明最后一個存活元素是索引2的0但它在邏輯展開后占兩個位置而數(shù)組只剩末尾一個空位了。也就是說這個0只能寫一次到arr[3]第二個0要被截斷。如果不在第二趟開始前把這個事處理掉倒寫時讀指針讀到索引2的0會往arr[3]和arr[2]連寫兩個0結(jié)果把數(shù)組搞得面目全非。正確的特判是if zeros 0 and i zeros n: arr[n - 1] 0 write - 1 read - 1先把能寫的那一個0放到數(shù)組末尾同時寫指針和讀指針各前移一格。這樣索引2的0就被視為“已經(jīng)完成了單次復(fù)制”不會再進入第二趟循環(huán)。推演一遍特判后 read 指向索引1write 指向索引2讀到索引1的0往arr[2]和arr[1]寫0讀到索引0的1往arr[0]寫1最終數(shù)組是[1, 0, 0, 0]和人工推演完全一致。3.3 Python 實現(xiàn)def duplicateZeros(arr): n len(arr) zeros 0 i 0 # 第一趟找出有效前綴邊界 while i zeros n: if arr[i] 0: zeros 1 i 1 # i 此時指向第一個不可能存活的位置減1得到有效前綴末尾 i - 1 write n - 1 # 邊界特判最后一個有效元素是0且只能寫一次 if zeros 0 and i zeros n: arr[write] 0 write - 1 i - 1 # 第二趟從后往前倒寫 while write 0: if arr[i] 0: arr[write] 0 write - 1 arr[write] 0 write - 1 else: arr[write] arr[i] write - 1 i - 1這段代碼里最值得注意的兩個地方第二趟的循環(huán)條件用write 0而不是i 0可以防止讀指針越界邊界特判里寫指針和讀指針都要同步前移。3.4 C 與 Java 實現(xiàn)C版本void duplicateZeros(vectorint arr) { int n arr.size(); int zeros 0; int i 0; while (i zeros n) { if (arr[i] 0) zeros; i; } i--; int write n - 1; if (zeros 0 i zeros n) { arr[write] 0; write--; i--; } while (write 0) { if (arr[i] 0) { arr[write] 0; write--; arr[write] 0; write--; } else { arr[write] arr[i]; write--; } i--; } }Java版本public void duplicateZeros(int[] arr) { int n arr.length; int zeros 0; int i 0; while (i zeros n) { if (arr[i] 0) zeros; i; } i--; int write n - 1; if (zeros 0 i zeros n) { arr[write] 0; write--; i--; } while (write 0) { if (arr[i] 0) { arr[write--] 0; arr[write--] 0; } else { arr[write--] arr[i]; } i--; } }三種語言的核心邏輯完全一致只是語法細(xì)節(jié)不同。Java里連續(xù)兩次write--簡寫在一行里注意別把指針移動次序搞反就行。3.5 復(fù)雜度分析第一趟循環(huán)最多掃描到n個元素就停第二趟倒寫也只需要處理有效前綴長度范圍內(nèi)的元素。兩趟加起來是嚴(yán)格O(n)即使是全0數(shù)組第一趟也會因為i zeros n快速退出。空間方面只用了zeros、i、write三個整數(shù)變量沒有開辟任何數(shù)組空間復(fù)雜度O(1)。時間上可能有人會問第二趟循環(huán)里遇到0會連寫兩次會不會多一次操作不會因為寫入這兩個0正好對應(yīng)它復(fù)寫后的兩個格子寫入次數(shù)和最終數(shù)組長度是一一對應(yīng)的。總體操作次數(shù)仍然和數(shù)組長度成正比。4. 最容易翻車的邊界條件4.1 末尾是0復(fù)寫一次還是兩次這是整道題最大的坑單獨拿出來說。判斷邏輯是如果最后一個“存活”的原始元素剛好是0而且它復(fù)寫后占兩個格子但數(shù)組只剩一個空位那么這個0只能復(fù)寫一次。寫成代碼就是i zeros n這個條件。我用四個例子做個速查表輸入邏輯展開后前n位代碼結(jié)果說明[1, 0, 0, 2][1, 0, 0, 0][1, 0, 0, 0]最后一個存活元素0只寫一次[0, 0, 1][0, 0, 0][0, 0, 0]邊界0占據(jù)最后格子[0, 0, 0][0, 0, 0][0, 0, 0]前兩個0占4格只剩3格[0, 1, 0][0, 0, 1][0, 0, 1]第二個0直接被截斷這幾個用例看著差不多但如果不做邊界特判反應(yīng)在結(jié)果上就是末尾多了一個0或中間少了一個0。4.2 空數(shù)組和單元素數(shù)組空數(shù)組就不說了什么循環(huán)都不會進入直接返回。單元素數(shù)組要看元素是不是0[0]復(fù)寫后邏輯上是[0, 0]截斷成[0]。第一趟掃描時i zeros 1i0時遇到0zeros變成1i變成1退出i1減到0i zeros 1 n觸發(fā)特判把arr[0] 0后 write變成-1read變成-1第二趟不執(zhí)行最終是[0]。[3]沒有0第一趟掃描后 zeros0不觸發(fā)特判第二趟把arr[0]原樣寫回最終[3]。這兩個小用例用來驗證代碼的健壯性特別好刷完題之后可以順手測一下。4.3 手工推演一個全0數(shù)組全0數(shù)組是很多人寫崩的場景。拿[0, 0, 0]來說邏輯上復(fù)寫后是6個0截斷成3個0看起來結(jié)果沒變化但代碼必須正確處理。第一趟掃描i0zeros0進入循環(huán)arr[0]0zeros變成1i變?yōu)?i1zeros11 1 3成立arr[1]0zeros變成2i變?yōu)?i2zeros22 2 3不成立退出退出后i 2減一變成1。此時i zeros 1 2 3 n觸發(fā)特判arr[2] 0write變成1i變成0。第二趟從 i0 開始讀到一個0寫兩格到arr[1]和arr[0]。最終仍然是三個0。如果不做特判第二趟從 i1 開始寫到后面就會發(fā)現(xiàn) write 已經(jīng)變負(fù)但讀指針還有元素沒處理或者最后多寫一個0導(dǎo)致數(shù)組被寫穿。運行時報錯還是小事靜默返回錯誤結(jié)果更可怕。4.4 常見錯誤速查表錯誤寫法錯誤后果正確做法第一趟循環(huán)用for i in range(n)多統(tǒng)計被截斷的0有效前綴偏移用while i zeros n卡邊界第二趟直接從read n - 1開始末尾原始數(shù)據(jù)可能被錯誤復(fù)制中間被覆蓋從有效前綴末尾開始邊界0不做特判數(shù)組末尾出現(xiàn)連續(xù)兩個0以外的錯位用i zeros n判斷并單寫一次第二趟條件寫成while i 0寫指針可能已經(jīng)出界但讀指針仍有殘留觸發(fā)越界用while write 0特判后只移動讀指針不移動寫指針邊界0被寫兩次后面數(shù)據(jù)錯位讀指針和寫指針都前移一格5. 一法通百法雙指針題的遷移思路5.1 三種雙指針模型數(shù)組題里的雙指針大致能分成三類快慢指針一個指針走得快一個走得慢常用于鏈表找環(huán)、數(shù)組去重。左右對撞指針一個從左邊走一個從右邊走常用于有序數(shù)組求和、反轉(zhuǎn)數(shù)組。讀寫指針一個負(fù)責(zé)讀原數(shù)組一個負(fù)責(zé)往結(jié)果位置寫常用于原地刪除、原地移動?！皬?fù)寫零”屬于第三種。這類題的核心判斷方式是如果目標(biāo)數(shù)組比原數(shù)組短一般從前往后用快慢指針如果目標(biāo)數(shù)組比原數(shù)組長基本要從后往前用讀寫指針。5.2 和“移動零”“原地去重”的對比原地去重這道題目標(biāo)數(shù)組比原數(shù)組短所以用一個慢指針指向“下一個不重復(fù)元素該放的位置”快指針從頭掃描原數(shù)組發(fā)現(xiàn)新元素就寫過去。這種從前往后沒問題因為快指針一定在慢指針前面或相等?！耙苿恿恪币彩峭粋€道理先把所有非零元素集中到前面再把后面全部補0。它不需要擴容所以從前往后寫完全安全。“復(fù)寫零”反過來目標(biāo)長度變長每一個0都要多占一個位置。此時從前往后寫寫指針會超過讀指針覆蓋未讀數(shù)據(jù)所以必須倒過來。合并兩個有序數(shù)組也是這個思路第一個數(shù)組尾部預(yù)留了足夠空間從后往前比較并寫入誰大誰先放根本不需要額外數(shù)組。總結(jié)成一句話目標(biāo)變長先找邊界再從后往前寫目標(biāo)變短快慢指針直接從前掃。5.3 面試?yán)镌趺纯焖僮R別這類題你看一個數(shù)組題如果要求原地修改先把最終長度和原始長度做比較。最終長度大于原始長度八成要用到“先擴容再倒寫”的思路最終長度小于或等于原始長度大概率是快慢指針的前向覆蓋?！皬?fù)寫零”表面上是模擬實際是“擴容式原地修改”的入門題。理解了它再去做“合并兩個有序數(shù)組”“字符串中的空格替換”這類題就會順暢很多因為它們共用同一套從后往前的直覺。6. 面試現(xiàn)場怎么在幾分鐘內(nèi)講清楚解法6.1 先給暴力解再談優(yōu)化面試遇到這題不用一上來就甩雙指針。先快速說一句“最直接的辦法是新開數(shù)組遇到0寫兩遍時間復(fù)雜度O(n)但空間O(n)不符合原地要求”。這能讓面試官知道你對復(fù)雜度有意識。然后說第二層“如果要在原地做就必須考慮覆蓋問題。數(shù)組要變長正序?qū)憰采w后續(xù)元素所以大概率倒序但倒序前必須知道哪些元素能活到最終數(shù)組里于是第一趟先數(shù)0、卡邊界?！?.2 把雙指針方案壓縮成三句話整個方案用三句話就能說清第一趟用i zeros n掃描找出有效前綴的末尾位置。如果末尾元素是0且它只夠?qū)懸淮螁为毺幚磉@個邊界0。第二趟從有效前綴末尾出發(fā)讀指針和寫指針一起向左移動遇0寫兩格遇非0寫一格?？谑鰰r強調(diào)“讀指針和寫指針不同速”“從后往前不會覆蓋未讀數(shù)據(jù)”“邊界0只寫一次”這三個點面試官基本就會點頭。6.3 我個人最推薦的代碼模板我在面試和平時刷題時習(xí)慣用的就是上面那套 Python 模板。它有幾個好處第一趟直接卡邊界不像某些寫法要先數(shù)完所有0再二次判斷邊界特判用i zeros n一目了然第二趟循環(huán)條件用write 0從根本上杜絕越界。def duplicateZeros(arr): n len(arr) zeros 0 i 0 while i zeros n: if arr[i] 0: zeros 1 i 1 i - 1 write n - 1 if zeros 0 and i zeros n: arr[write] 0 write - 1 i - 1 while write 0: if arr[i] 0: arr[write] 0 write - 1 arr[write] 0 write - 1 else: arr[write] arr[i] write - 1 i - 1這個模板可以直接背更重要的是每次寫完都手動跑一遍[1, 0, 0, 2]、[0, 0, 1]、[0, 0, 0]、[1, 0, 2, 3, 0, 4, 5, 0]這四個用例基本就能確認(rèn)邊界處理沒有問題。6.4 刷題建議與復(fù)盤心得這道題很適合放進“數(shù)組原地操作”專題里反復(fù)練習(xí)。第一次做建議先不看題解自己把正序的失敗過程推演一遍感受數(shù)據(jù)被覆蓋的瞬間第二次做再去看雙指針解法重點理解第一趟為什么能卡邊界第三次做可以把代碼默寫出來并主動給面試官講“如果最后一個有效元素是0會怎樣”。我自己帶人刷題時發(fā)現(xiàn)最容易卡住的地方不是雙指針本身而是那個邊界特判。很多人第一趟掃描寫對了但第二趟忘記處理“只夠?qū)懸淮蔚?”導(dǎo)致結(jié)果在末尾多出一個錯位。把[1, 0, 0, 2]這個用例刻進腦子里這個坑基本就不會再踩?！皬?fù)寫零”這類題還有一個隱藏價值它逼你跳出“從前往后”的思維慣性。實際開發(fā)里處理緩沖區(qū)擴容、日志滾動、歷史版本合并時從后往前寫都是一個很實用的技巧。刷題的價值有時候不在記住某個模板而在把這種“倒過來想”的直覺訓(xùn)練成本能。