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