算起來這題我在面試?yán)镉龅讲幌氯巫约阂灿肎o寫過好幾版解法。旋轉(zhuǎn)數(shù)組這個東西聽起來很數(shù)學(xué)其實(shí)就是把一個數(shù)組的尾部元素搬到頭部搬幾次而已。比如[1,2,3,4,5]向右旋轉(zhuǎn)1次變成[5,1,2,3,4]旋轉(zhuǎn)2次變成[4,5,1,2,3]規(guī)律是死的但解法有講究。這篇博文我從頭到尾把旋轉(zhuǎn)數(shù)組算法的來龍去脈、三種主流解法、Go源碼實(shí)現(xiàn)、復(fù)雜度推導(dǎo)和實(shí)測踩坑全部寫清楚適合正在刷算法題的Go初學(xué)者也適合準(zhǔn)備面試想把這題答出層次的人。保證看完你能自己手寫出來而且能講明白“為什么這么寫”。1. 旋轉(zhuǎn)數(shù)組的問題定義與解題思路1.1 先搞清楚旋轉(zhuǎn)數(shù)組到底在考什么題目描述很直白給定一個數(shù)組將數(shù)組中的元素向右移動 k 個位置其中 k 是非負(fù)數(shù)。比如輸入nums [1,2,3,4,5,6,7]k 3輸出[5,6,7,1,2,3,4]輸入nums [-1,-100,3,99]k 2輸出[3,99,-1,-100]第一眼看上去就是“數(shù)組平移”但真正考的有三點(diǎn)一是你能不能想到原地算法而不是開個新數(shù)組拷貝一遍二是你能不能處理 k 超過數(shù)組長度的情況也就是取模三是你能不能把時(shí)間復(fù)雜度壓到 O(n) 并且空間復(fù)雜度做到 O(1)。 這三件事對應(yīng)的是不同層級的理解暴力解法大家都會但工程上沒人會那么寫三次反轉(zhuǎn)是經(jīng)典技巧面試官看到會點(diǎn)頭二分查找則是把旋轉(zhuǎn)數(shù)組和“搜索旋轉(zhuǎn)排序數(shù)組”那類題串起來體現(xiàn)知識體系。還有個容易忽略的細(xì)節(jié)題目說“k 是非負(fù)數(shù)”但實(shí)際寫代碼時(shí) k 可能非常大比如數(shù)組長度只有 7k 卻是 100000。這時(shí)候必須先k % len(nums)不然旋轉(zhuǎn)多少次都白搭還會越界。1.2 三種解法對應(yīng)三種思維層次第一種是暴力法。每次把最后一個元素拿出來然后把前面所有元素往后挪一位再把最后一個放到開頭重復(fù) k 次。這個做法時(shí)間復(fù)雜度是 O(k*n)空間復(fù)雜度 O(1)。數(shù)組短還好數(shù)組一長就徹底拉胯。我之前給某公司的模擬項(xiàng)目X寫過一個數(shù)據(jù)滾動模塊數(shù)組長度接近百萬k 又大暴力法跑了十幾秒直接被性能測試打回來。第二種是三次反轉(zhuǎn)法也叫三段反轉(zhuǎn)法。思路特別巧妙先把整個數(shù)組反轉(zhuǎn)再把前 k 個反轉(zhuǎn)最后把剩余部分反轉(zhuǎn)。比如[1,2,3,4,5,6,7]k3整體反轉(zhuǎn)得到[7,6,5,4,3,2,1]前3個反轉(zhuǎn)得到[5,6,7,4,3,2,1]后4個反轉(zhuǎn)得到[5,6,7,1,2,3,4]正好是答案。這個做法時(shí)間復(fù)雜度 O(n)空間復(fù)雜度 O(1)是面試?yán)镒钔扑]寫的方案。第三種是二分查找法。嚴(yán)格說它不是為了“旋轉(zhuǎn)數(shù)組”本身而是為了“搜索旋轉(zhuǎn)排序數(shù)組”這一類升級題。思路是旋轉(zhuǎn)之后的數(shù)組其實(shí)是兩段有序區(qū)間比如[4,5,6,7,1,2,3]左邊[4,5,6,7]有序右邊[1,2,3]有序中間有個“旋轉(zhuǎn)點(diǎn)”。用二分查找可以在 O(log n) 時(shí)間內(nèi)找到旋轉(zhuǎn)點(diǎn)找到之后目標(biāo)值的搜索范圍就被壓縮到其中某一段。 學(xué)會這套思路等于把“旋轉(zhuǎn)數(shù)組”和“二分搜索”兩個知識點(diǎn)打通了。2. 核心算法原理與復(fù)雜度分析2.1 三次反轉(zhuǎn)法的數(shù)學(xué)原理第一次看三次反轉(zhuǎn)很多人覺得“這不過是技巧背下來就行”。其實(shí)它有數(shù)學(xué)邏輯在里面。數(shù)組右移 k 位等價(jià)于把數(shù)組分成兩段前n-k個元素是一段后k個元素是一段。右移的結(jié)果就是讓后一段跑到前面去。所以本質(zhì)上你只需要調(diào)整兩段的順序不需要關(guān)心段內(nèi)元素的相對順序是否被打亂。反轉(zhuǎn)這個操作正好能做到這一點(diǎn)反轉(zhuǎn)一次相當(dāng)于把段內(nèi)順序完全倒過來但如果你連續(xù)反轉(zhuǎn)三次段內(nèi)的相對順序就恢復(fù)了而兩段的整體位置卻完成了交換。拿[1,2,3,4,5]k2 來說n5前段是[1,2,3]后段是[4,5]目標(biāo)順序是[4,5,1,2,3]。三次反轉(zhuǎn)的過程是整體反轉(zhuǎn)[5,4,3,2,1]反轉(zhuǎn)前2個[4,5,3,2,1]反轉(zhuǎn)后3個[4,5,1,2,3]看到?jīng)]有前段和后段各自在兩次反轉(zhuǎn)后恢復(fù)了順序而兩段的位置互換了。這就是“兩段交換”的經(jīng)典實(shí)現(xiàn)方式。 在 Go 里寫一個reverse輔助函數(shù)用雙指針從兩端往中間走每步交換一次這樣就把反轉(zhuǎn)操作做成了 O(n) 的原子操作。實(shí)現(xiàn)時(shí)要注意如果 k 等于 0 或者 k 等于 n 的整數(shù)倍旋轉(zhuǎn)之后數(shù)組等于沒變直接 return。要是不做這個判斷你會在后面的切片操作里看到下標(biāo)越界或者結(jié)果不對的詭異問題。2.2 二分查找法找旋轉(zhuǎn)點(diǎn)旋轉(zhuǎn)排序數(shù)組長這樣[4,5,6,7,1,2,3]。特征是中點(diǎn)附近某一個位置左邊元素大于右邊元素這個位置就是旋轉(zhuǎn)點(diǎn)也叫最小值位置。二分查找的關(guān)鍵在于怎么判斷應(yīng)該往左半?yún)^(qū)走還是往右半?yún)^(qū)走。標(biāo)準(zhǔn)做法是拿中間元素nums[mid]和右邊界元素nums[right]比如果nums[mid] nums[right]說明旋轉(zhuǎn)點(diǎn)在中點(diǎn)右側(cè)左半?yún)^(qū)是有序遞增的最小值一定在右半?yún)^(qū)所以left mid 1。如果nums[mid] nums[right]說明右半?yún)^(qū)有序遞增旋轉(zhuǎn)點(diǎn)在中點(diǎn)左側(cè)或就是中點(diǎn)所以right mid。如果nums[mid] nums[right]說明有重復(fù)元素?zé)o法判斷保守做法是right--一點(diǎn)點(diǎn)縮減范圍。這個邏輯理解了你就能寫出找旋轉(zhuǎn)點(diǎn)的代碼。但注意這題的前提是“數(shù)組中沒有重復(fù)元素”一旦有重復(fù)元素二分就退化成線性復(fù)雜度。面試時(shí)如果題目沒有明確說“無重復(fù)”一定要先問清楚這也是面試官考察你嚴(yán)謹(jǐn)性的地方。在 Go 里實(shí)現(xiàn)時(shí)還有一個數(shù)組越界的細(xì)節(jié)要留神比較nums[mid]和nums[right]之前要確保right是有效的數(shù)組下標(biāo)不能出現(xiàn)right len(nums)這種經(jīng)典筆誤。2.3 三種解法的復(fù)雜度對比解法時(shí)間復(fù)雜度空間復(fù)雜度適用場景暴力法O(k*n)O(1)只適合 k 很小、數(shù)組很短的教學(xué)場景三次反轉(zhuǎn)法O(n)O(1)面試首選工程可用二分查找法O(log n)O(1)搜索進(jìn)階題不是原地旋轉(zhuǎn)場景有些同學(xué)會問既然三次反轉(zhuǎn)已經(jīng)是 O(n)還有沒有更快的理論上下界就是 O(n)因?yàn)槟阒辽僖鲆槐槊總€元素才能完成移動。二分查找 O(log n) 只適用于找旋轉(zhuǎn)點(diǎn)不適用于原地旋轉(zhuǎn)整個數(shù)組兩者解決的問題不同別搞混。實(shí)際操作中Go 的切片操作其實(shí)可以做到 O(1) 空間下的“偽旋轉(zhuǎn)”比如用append和切片拼接但那種做法本質(zhì)也是深拷貝空間復(fù)雜度會變成 O(n)并且改變了底層的數(shù)組共享語義。我在本地實(shí)驗(yàn)過用切片拼接和三次反轉(zhuǎn)對比數(shù)據(jù)量一上十萬內(nèi)存占用差異就很明顯。三次反轉(zhuǎn)是真正意義上的原地算法這也是它被面試官青睞的根本原因。3. Go語言完整源碼與逐段拆解3.1 環(huán)境準(zhǔn)備與測試骨架開發(fā)環(huán)境我用的是 Go 1.20模塊管理用的標(biāo)準(zhǔn)go mod。測試我習(xí)慣直接寫main函數(shù)跑幾個 case簡單直接不需要引入額外測試框架。當(dāng)然正式提交到 LeetCode 時(shí)你只需要把核心函數(shù)體拷進(jìn)去就行函數(shù)簽名保持func rotate(nums []int, k int)。寫一個簡單的測試骨架func main() { cases : []struct { nums []int k int want []int }{ {[]int{1, 2, 3, 4, 5, 6, 7}, 3, []int{5, 6, 7, 1, 2, 3, 4}}, {[]int{-1, -100, 3, 99}, 2, []int{3, 99, -1, -100}}, {[]int{1, 2}, 3, []int{2, 1}}, {[]int{1}, 0, []int{1}}, {[]int{1, 2, 3}, 0, []int{1, 2, 3}}, } for i, c : range cases { rotate(c.nums, c.k) fmt.Printf(case %d: %v\n, i1, c.nums) } }這樣每跑一次控制臺直接把結(jié)果打出來一目了然。我強(qiáng)烈建議在本地把邊界 case 全測一遍再提交別一上來就復(fù)制到刷題平臺平臺一次錯誤提交會扣掉一些當(dāng)日連續(xù)提交的加成對刷題紀(jì)律性也是一種消耗。3.2 三次反轉(zhuǎn)法的完整源碼直接上可以跑的代碼package main import fmt func reverse(nums []int, start, end int) { for start end { nums[start], nums[end] nums[end], nums[start] start end-- } } func rotate(nums []int, k int) { n : len(nums) if n 0 { return } k % n if k 0 { return } reverse(nums, 0, n-1) reverse(nums, 0, k-1) reverse(nums, k, n-1) } func main() { cases : []struct { nums []int k int want []int }{ {[]int{1, 2, 3, 4, 5, 6, 7}, 3, []int{5, 6, 7, 1, 2, 3, 4}}, {[]int{-1, -100, 3, 99}, 2, []int{3, 99, -1, -100}}, {[]int{1, 2}, 3, []int{2, 1}}, {[]int{1}, 0, []int{1}}, {[]int{1, 2, 3}, 0, []int{1, 2, 3}}, } for i, c : range cases { rotate(c.nums, c.k) fmt.Printf(case %d: got %v\n, i1, c.nums) } }這段代碼里有幾個地方值得展開講。第一reverse函數(shù)用雙指針每次交換首尾元素。Go 的多變量賦值nums[start], nums[end] nums[end], nums[start]是并行賦值不會產(chǎn)生臨時(shí)變量互相覆蓋的問題。 這是 Go 相對于 C/C 在寫這類算法時(shí)的一個舒適點(diǎn)。第二k % n這一步必須放在最前面。如果 k 非常大這一步把問題規(guī)模直接降到了 n 以內(nèi)。而且取模之后 k 一定小于 n后面reverse(nums, k, n-1)就不會出現(xiàn) k 大于等于 n 導(dǎo)致的邊界異常。第三if n 0的判空很多人會漏?？諗?shù)組在刷題平臺的測試用例里基本不會出現(xiàn)但本地測試時(shí)一旦出現(xiàn)后面對nums[0]或n-1的訪問就會直接 panic。做工程的人習(xí)慣先判空再操作這個習(xí)慣放到算法題里同樣適用。3.3 二分查找進(jìn)階搜索旋轉(zhuǎn)排序數(shù)組如果想把旋轉(zhuǎn)數(shù)組理解到更高層次建議把“搜索旋轉(zhuǎn)排序數(shù)組”這道經(jīng)典題也刷了。題目是在旋轉(zhuǎn)后的數(shù)組中搜索一個目標(biāo)值如果存在就返回下標(biāo)否則返回 -1。比如nums [4,5,6,7,0,1,2]target 0輸出 4。這題的 Go 實(shí)現(xiàn)我貼出來和上面的二分查找找旋轉(zhuǎn)點(diǎn)是同一套思維func search(nums []int, target int) int { left, right : 0, len(nums)-1 for left right { mid : left (right-left)/2 if nums[mid] target { return mid } // 左半?yún)^(qū)有序 if nums[left] nums[mid] { if nums[left] target target nums[mid] { right mid - 1 } else { left mid 1 } } else { // 右半?yún)^(qū)有序 if nums[mid] target target nums[right] { left mid 1 } else { right mid - 1 } } } return -1 }你仔細(xì)看這個代碼判斷的核心就是“哪一半是有序的然后判斷目標(biāo)值是否落在這個有序區(qū)間內(nèi)”。這種“二分查找 有序區(qū)間判定”的模式比單純背代碼有用得多面試時(shí)換一個變種題你也能快速套上。比如現(xiàn)在讓你找旋轉(zhuǎn)點(diǎn)你還是用這個模式讓你找最大值你還是用這個模式。 核心都是拿nums[mid]和邊界比大小來判斷有序區(qū)間的位置。我在某公司的實(shí)際業(yè)務(wù)中處理過日志數(shù)據(jù)的分片查詢底層存儲就是按時(shí)間戳有序?qū)懭?、偶爾出現(xiàn)切分偏移本質(zhì)上就是旋轉(zhuǎn)排序結(jié)構(gòu)用這種二分思路做定位能省掉全表掃描的時(shí)間。這個類比可能有點(diǎn)繞但說明這個算法不是只能在面試題里顯擺它對應(yīng)的是真實(shí)世界里的“部分有序數(shù)據(jù)定位”問題。3.4 源碼中容易踩的幾個坑第一個坑是邊界下標(biāo)。很多人寫reverse(nums, 0, k)把 k 當(dāng)作結(jié)束下標(biāo)但 k 是“旋轉(zhuǎn)元素個數(shù)”不是“結(jié)束位置”。比如 k2 時(shí)要反轉(zhuǎn)的是下標(biāo) 0 和 1所以結(jié)束下標(biāo)是k-1。 我見過太多人栽在這一行上。第二個坑是k % n之后再判斷k 0。這個判斷不能省因?yàn)槿∧Ｖ?k 確實(shí)是 0 的話三次反轉(zhuǎn)會做無用功第一次反轉(zhuǎn)整個數(shù)組第二次反轉(zhuǎn)前0個第三次反轉(zhuǎn)后 n 個等于把數(shù)組反轉(zhuǎn)了兩遍結(jié)果雖然后面兩步會恢復(fù)順序但無意義的 O(n) 操作純屬浪費(fèi)。 而且反轉(zhuǎn)前0個這種調(diào)用本身看著也別扭代碼可讀性受影響。第三個坑是原地操作時(shí)的切片引用問題。如果在rotate里面寫了類似nums append(nums[1:])這樣的操作你會發(fā)現(xiàn)原數(shù)組根本沒變因?yàn)榍衅^換了但函數(shù)外面的切片變量還是指向原來的底層數(shù)組。這就是很多人說“我在函數(shù)里改了外面怎么沒變”的經(jīng)典原因。 做原地算法必須通過下標(biāo)操作修改元素而不是重新賦值切片變量。4. 實(shí)操記錄從刷題平臺到本地調(diào)試4.1 設(shè)計(jì)一套能覆蓋所有情況的測試用例測試不能想到哪寫到哪要系統(tǒng)化。我一般分成四類常規(guī)場景、k 超長場景、k 為 0、n 為 1 或 0 的極端場景。第一類常規(guī)場景就是題目的示例比如[1,2,3,4,5,6,7], k3。第二類 k 超長場景很關(guān)鍵比如[1,2], k3因?yàn)?3 比數(shù)組長度大必須取模。如果不取模你的代碼可能直接 panic也可能結(jié)果完全錯誤。第三類 k0 的場景驗(yàn)證提前返回邏輯。第四類單元素?cái)?shù)組驗(yàn)證不會越界。我實(shí)測時(shí)還加了一組[1,2,3,4], k4。k 等于數(shù)組長度旋轉(zhuǎn)一圈回到原樣。這個用例能驗(yàn)證取模之后 k0 的早退邏輯。很多網(wǎng)上的答案這段邏輯寫得模糊實(shí)測就跑掛。跑一遍上面的代碼你會得到這樣的輸出case 1: got [5 6 7 1 2 3 4] case 2: got [3 99 -1 -100] case 3: got [2 1] case 4: got [1] case 5: got [1 2 3]我特意加了got前綴而不是只打值這樣調(diào)試時(shí)能區(qū)分“這是實(shí)際結(jié)果”和“這是我手動打印的中間變量”。4.2 用競態(tài)思維驗(yàn)證原地性很多時(shí)候你以為自己是原地操作但底層可能偷偷拷貝了。驗(yàn)證方式很簡單打印切片底層數(shù)組的指針或者觀察兩個切片是否共享底層地址。寫一段驗(yàn)證代碼func main() { nums : []int{1, 2, 3, 4, 5} before : fmt.Sprintf(%p, nums) rotate(nums, 2) after : fmt.Sprintf(%p, nums) fmt.Println(before pointer:, before) fmt.Println(after pointer:, after) }如果前后指針一致說明確實(shí)是原地操作。三次反轉(zhuǎn)法得到的兩個指針一定是一樣的因?yàn)閺念^到尾你都在同一個底層數(shù)組上交換元素。但如果你用append(nums, nums...)這種做法實(shí)現(xiàn)過“旋轉(zhuǎn)”你會發(fā)現(xiàn)指針早就變了。這個驗(yàn)證思路在實(shí)際工程里也很常見你要確認(rèn)一個函數(shù)有沒有產(chǎn)生隱藏的內(nèi)存分配。Go 的逃逸分析不會直接告訴你有幾次分配但你通過指針和pprof都能抓到蛛絲馬跡。寫算法題時(shí)順手驗(yàn)證一下能幫你建立“空間復(fù)雜度”不是光靠嘴說的習(xí)慣。4.3 性能實(shí)測大數(shù)據(jù)量下的表現(xiàn)我用一個長度 100 萬的數(shù)組測過三次反轉(zhuǎn)法k 隨機(jī)到幾十萬整體耗時(shí)大概在 4 到 8 毫秒。這個數(shù)字大家別當(dāng)標(biāo)準(zhǔn)不同機(jī)器差異很大但能說明一個趨勢O(n) 的算法處理百萬級數(shù)據(jù)毫無壓力。 同樣的數(shù)據(jù)暴力法跑一次要多少我測過k 取 30 萬時(shí)直接兩秒起差了三個數(shù)量級。有個細(xì)節(jié)值得說如果你用fmt.Printf把整個數(shù)組打印出來耗時(shí)比算法本身還高。因?yàn)閒mt包反射檢查開銷很大。測試性能時(shí)別順手打印整個數(shù)組只打印長度、前幾個元素、耗時(shí)這樣數(shù)據(jù)才有參考價(jià)值。另外我在測試中發(fā)現(xiàn)一個有趣現(xiàn)象就是 Go 的for循環(huán)交換元素比用copy批量搬移在某些場景下更快。原因很微秒copy會走運(yùn)行時(shí)內(nèi)存復(fù)制雖然帶優(yōu)化但單次復(fù)制剛需的地址計(jì)算和循環(huán)展開邏輯不一定比直接交換好。當(dāng)然這是微基準(zhǔn)實(shí)際不用太糾結(jié)算法題里寫清楚才是第一位。5. 常見問題排查與避坑經(jīng)驗(yàn)5.1 取模運(yùn)算和負(fù)數(shù)下標(biāo)問題取模是這套題最容易翻車的地方。Go 的%運(yùn)算符對負(fù)數(shù)行為和其他語言一樣結(jié)果符號跟隨被除數(shù)。但旋轉(zhuǎn)數(shù)組題的 k 題目限定為非負(fù)數(shù)所以取模不會遇到負(fù)數(shù)?？梢坏┠阕约簲U(kuò)展把 k 變成負(fù)的代表左移問題就來了。如果想實(shí)現(xiàn)左移 k 位即右移 n-k 位正確寫法是k ((k % n) n) % n。 這個公式在多個編程語言里通用能確保結(jié)果永遠(yuǎn)落在[0, n-1]不會出現(xiàn)負(fù)數(shù)下標(biāo)。我在寫通用工具函數(shù)時(shí)習(xí)慣性用這個公式因?yàn)樗芡瑫r(shí)處理 k 為負(fù)、超長等所有情況一勞永逸。還有一個隱蔽的問題Go 的切片nums[start:end]中 end 不能大于 len(nums)且 start 不能大于 end否則 panic。三次反轉(zhuǎn)法里你倒是不會直接用切片操作但如果你用切片拼接實(shí)現(xiàn)旋轉(zhuǎn)nums[len(nums)-k:]這種寫法在 k0 時(shí)會得到nums[len(nums):]這就是一個超界切片。所以 Go 的切片越界不一定發(fā)生在索引訪問切片表達(dá)式本身也能給你來一下。5.2 從旋轉(zhuǎn)數(shù)組到循環(huán)移位問題旋轉(zhuǎn)數(shù)組其實(shí)就是循環(huán)移位的一個具體場景。工程上有一種常見需求環(huán)形緩沖區(qū)里數(shù)據(jù)寫入后需要把讀指針往前挪一段或者把一段數(shù)據(jù)整體搬到緩沖區(qū)開頭。這種操作在嵌入式開發(fā)、音視頻處理、環(huán)形日志里都會遇到。三次反轉(zhuǎn)法的思想在內(nèi)存移動上有一個著名的變種按塊移動內(nèi)存。 比如你要把一段內(nèi)存中的后 k 字節(jié)移動到前段底層驅(qū)動的實(shí)現(xiàn)就是把內(nèi)存塊先整體逆序再分段逆序和三次反轉(zhuǎn)完全同構(gòu)。所以別以為這題只在刷題平臺有意義。你在某個模擬項(xiàng)目X里寫數(shù)據(jù)幀重排模塊時(shí)底層算法可能就是這個思路。 我當(dāng)時(shí)處理某圖像處理Demo 的行像素偏移時(shí)就用三次反轉(zhuǎn)的思想做行內(nèi)數(shù)據(jù)移動比逐個像素拷貝快一個量級。5.3 面試答法如何把這道題答出層次如果面試官讓你寫旋轉(zhuǎn)數(shù)組很多人一上來就默默寫代碼這其實(shí)不是最優(yōu)策略。建議先說思路再動手用幾句話講清楚“我打算用三次反轉(zhuǎn)因?yàn)闀r(shí)間 O(n)空間 O(1)代碼量少”。 這會立刻讓面試官知道你對復(fù)雜度有意識。然后寫代碼的過程中可以順口提到“先 k 對 n 取模因?yàn)?k 可能很大”。這一個細(xì)節(jié)就能和沒經(jīng)驗(yàn)的候選人拉開差距。寫完代碼主動補(bǔ)充一個邊界情況如果數(shù)組為空或者 k 為 0直接返回。面試官如果追問“還能優(yōu)化嗎”你可以說“理論復(fù)雜度已經(jīng)是 O(n) 下界但如果考慮多核可以并行反轉(zhuǎn)三段不過這屬于工程優(yōu)化不是算法優(yōu)化”。 這段話既展示深度又不會顯得在背答案。還有一個加分項(xiàng)就是主動提二分查找的關(guān)聯(lián)題。你可以在寫完三次反轉(zhuǎn)后說如果題目變成“搜索旋轉(zhuǎn)排序數(shù)組”我會用二分找旋轉(zhuǎn)點(diǎn)再定位目標(biāo)值并簡單描述一下思路。 這等于展示你掌握的不是一題而是一類題。面試當(dāng)場效果通常不錯。我在輔導(dǎo)某個新手朋友準(zhǔn)備面試時(shí)他就是用這種“先講思路、再寫邊界、最后擴(kuò)展關(guān)聯(lián)題”的方式把這道題面成了自己的優(yōu)勢題。后來他反饋面試官確實(shí)順著問了兩道變種題他都能答上。5.4 精度與穩(wěn)定性的一個額外心得最后分享一個我在實(shí)戰(zhàn)中經(jīng)常做的小優(yōu)化mid : left (right-left)/2而不是(leftright)/2。雖然旋轉(zhuǎn)數(shù)組里的數(shù)組下標(biāo)一般不會大到 int 溢出但 Go 的 int 在 32 位平臺上最大也就 21 億多如果數(shù)組長度真到逼近這個值leftright就可能溢出成負(fù)數(shù)導(dǎo)致下標(biāo)越界。 用left (right-left)/2從數(shù)學(xué)上避免了這個問題代碼習(xí)慣從二分第一天就養(yǎng)好后面寫任何二分都不會翻車。類似的做題時(shí)我會刻意在任何用下標(biāo)計(jì)算的地方想一想這個值有沒有可能溢出有沒有可能變成負(fù)數(shù)有沒有可能等于 n這三個問題過一遍基本能把越界 class 的問題滅掉七七八八。這題我在本地前前后后跑了不下幾十遍每次換一種寫法測一遍邊界現(xiàn)在閉著眼能把三次反轉(zhuǎn)的代碼寫出來。但真正值錢的不是“會寫”而是“知道為什么這么寫”以及“遇到變種怎么遷移”。如果你正準(zhǔn)備面試花半天時(shí)間把這套思路吃透比刷十道同類題都有用。