原地哈希是算法題里一種很實(shí)用的技巧它能在不申請(qǐng)額外空間的情況下利用輸入數(shù)組自身的空間來(lái)記錄狀態(tài)或完成排序。這種思路在解決“找出數(shù)組中重復(fù)或缺失的數(shù)字”這類問(wèn)題時(shí)特別高效。很多人第一次接觸原地哈希會(huì)覺(jué)得有點(diǎn)繞因?yàn)樗竽阍谛薷臄?shù)組的同時(shí)還要利用修改后的信息繼續(xù)處理。這就像是在整理書(shū)架時(shí)不僅要找出放錯(cuò)位置的書(shū)還要利用書(shū)架上現(xiàn)有的空位或錯(cuò)位信息來(lái)最終歸位整個(gè)過(guò)程不能借助額外的書(shū)架。下面我會(huì)用一個(gè)具體的 LeetCode 經(jīng)典問(wèn)題——「尋找數(shù)組中重復(fù)的數(shù)字」來(lái)拆解原地哈希的完整思路和實(shí)現(xiàn)細(xì)節(jié)。我會(huì)先講清楚為什么這道題適合用原地哈希再一步步帶你寫出可運(yùn)行的代碼最后給出排查邊界情況的實(shí)用建議。1. 先理解原地哈希到底解決了什么問(wèn)題原地哈希最典型的應(yīng)用場(chǎng)景是給定一個(gè)長(zhǎng)度為 n 的數(shù)組數(shù)組中的元素是 1 到 n 之間的整數(shù)但其中可能有重復(fù)或缺失。題目要求找出重復(fù)的數(shù)字或缺失的數(shù)字但空間復(fù)雜度必須為 O(1)即不能使用額外的哈希表或集合。1.1 為什么不能直接用哈希表如果允許使用額外空間這道題非常簡(jiǎn)單遍歷數(shù)組把每個(gè)數(shù)字放入哈希表遇到已經(jīng)存在的數(shù)字就是重復(fù)項(xiàng)。但很多面試題和競(jìng)賽題會(huì)限制空間復(fù)雜度這就要求我們必須在原數(shù)組上做文章。原地哈希的核心思想是“讓數(shù)字回到它本該在的位置”。比如數(shù)字 3 應(yīng)該放在索引 2 的位置如果數(shù)組從 0 開(kāi)始索引數(shù)字 1 應(yīng)該放在索引 0 的位置。通過(guò)交換操作我們一邊排序一邊檢查重復(fù)。1.2 原地哈希的適用條件不是所有問(wèn)題都適合用原地哈希它需要滿足以下條件數(shù)組元素的值域與索引范圍有對(duì)應(yīng)關(guān)系通常是 1 到 n 對(duì)應(yīng)索引 0 到 n-1允許修改原數(shù)組空間復(fù)雜度要求嚴(yán)格不能使用額外數(shù)據(jù)結(jié)構(gòu)常見(jiàn)的 LeetCode 題目包括尋找重復(fù)數(shù)找到所有數(shù)組中消失的數(shù)字缺失的第一個(gè)正數(shù)這些題目都可以用原地哈希的思路解決。2. 原地哈希的具體實(shí)現(xiàn)步驟下面我以「尋找重復(fù)數(shù)字」為例詳細(xì)拆解原地哈希的實(shí)現(xiàn)過(guò)程。2.1 基本思路數(shù)字歸位假設(shè)數(shù)組為nums [3, 1, 3, 4, 2]長(zhǎng)度為 5數(shù)字范圍是 1 到 5包含重復(fù)。原地哈希的做法是遍歷數(shù)組對(duì)于每個(gè)位置 i檢查 nums[i] 是否等于 i1如果不等于就把 nums[i] 放到它應(yīng)該在的位置索引為 nums[i]-1在交換前先檢查目標(biāo)位置是否已經(jīng)存在正確的數(shù)字如果是說(shuō)明找到重復(fù)2.2 代碼實(shí)現(xiàn)細(xì)節(jié)def findDuplicate(nums): n len(nums) i 0 while i n: # 如果當(dāng)前數(shù)字已經(jīng)在正確位置繼續(xù)下一個(gè) if nums[i] i 1: i 1 continue # 計(jì)算當(dāng)前數(shù)字應(yīng)該在的位置 correct_pos nums[i] - 1 # 如果目標(biāo)位置的數(shù)字已經(jīng)是正確的說(shuō)明當(dāng)前數(shù)字是重復(fù)的 if nums[correct_pos] nums[i]: return nums[i] # 否則交換兩個(gè)位置的數(shù)字 nums[i], nums[correct_pos] nums[correct_pos], nums[i] return -1 # 理論上不會(huì)執(zhí)行到這里因?yàn)橐欢ㄓ兄貜?fù)2.3 一步步跟蹤執(zhí)行過(guò)程用nums [3, 1, 3, 4, 2]來(lái)演示第一次迭代 (i0)nums[0] 3應(yīng)該在位置 2索引 2檢查 nums[2] 3與 nums[0] 相等 → 找到重復(fù)數(shù)字 3直接返回 3這個(gè)例子比較特殊第一次就找到了重復(fù)。我們換一個(gè)例子nums [1, 3, 4, 2, 2]第一次迭代 (i0)nums[0] 1已經(jīng)在正確位置 → i第二次迭代 (i1)nums[1] 3應(yīng)該在位置 2索引 2nums[2] 4 ≠ 3 → 交換[1, 4, 3, 2, 2]繼續(xù) i1交換后當(dāng)前位置數(shù)字變了nums[1] 4應(yīng)該在位置 3索引 3nums[3] 2 ≠ 4 → 交換[1, 2, 3, 4, 2]繼續(xù) i1nums[1] 2應(yīng)該在位置 1索引 1→ 正確 → i第三次迭代 (i2)nums[2] 3正確 → i第四次迭代 (i3)nums[3] 4正確 → i第五次迭代 (i4)nums[4] 2應(yīng)該在位置 1索引 1nums[1] 2與 nums[4] 相等 → 找到重復(fù)數(shù)字 23. 原地哈希的邊界情況和排查要點(diǎn)雖然原地哈希的思路很清晰但實(shí)際實(shí)現(xiàn)時(shí)容易遇到各種邊界問(wèn)題。下面是我在實(shí)際編碼和調(diào)試中總結(jié)的幾個(gè)關(guān)鍵點(diǎn)。3.1 避免無(wú)限循環(huán)原地哈希最容易出現(xiàn)的問(wèn)題就是無(wú)限循環(huán)。比如這樣的代碼# 錯(cuò)誤示例可能導(dǎo)致無(wú)限循環(huán) for i in range(n): while nums[i] ! i 1: correct_pos nums[i] - 1 nums[i], nums[correct_pos] nums[correct_pos], nums[i]問(wèn)題在于如果交換后 nums[i] 仍然不在正確位置會(huì)繼續(xù)交換但可能陷入循環(huán)。更安全的做法是使用外層 while 循環(huán)配合條件判斷。3.2 處理重復(fù)數(shù)字的判斷時(shí)機(jī)判斷重復(fù)的時(shí)機(jī)很重要應(yīng)該在交換前檢查目標(biāo)位置是否已經(jīng)是正確的數(shù)字。如果先交換再檢查會(huì)漏掉一些情況。正確的判斷邏輯# 在交換前檢查目標(biāo)位置 if nums[correct_pos] nums[i]: return nums[i] # 找到重復(fù)3.3 索引邊界檢查雖然理論上數(shù)字都在 1 到 n 范圍內(nèi)但實(shí)際題目中可能有特殊情況。穩(wěn)妥的做法是添加邊界檢查def findDuplicate(nums): n len(nums) i 0 while i n: # 如果當(dāng)前數(shù)字不在有效范圍內(nèi)跳過(guò) if nums[i] 1 or nums[i] n: i 1 continue correct_pos nums[i] - 1 # 如果已經(jīng)在正確位置 if correct_pos i: i 1 continue # 檢查重復(fù) if nums[correct_pos] nums[i]: return nums[i] # 交換 nums[i], nums[correct_pos] nums[correct_pos], nums[i] return -14. 原地哈希的變種和應(yīng)用擴(kuò)展原地哈希不僅適用于找重復(fù)數(shù)字經(jīng)過(guò)適當(dāng)修改可以解決更多問(wèn)題。4.1 找出所有消失的數(shù)字LeetCode 448 題要求找出 1 到 n 中所有沒(méi)有出現(xiàn)在數(shù)組中的數(shù)字。思路類似但需要標(biāo)記出現(xiàn)過(guò)的數(shù)字def findDisappearedNumbers(nums): n len(nums) # 第一遍遍歷用原地哈希標(biāo)記出現(xiàn)過(guò)的數(shù)字 for i in range(n): # 計(jì)算數(shù)字應(yīng)該在的位置 correct_pos abs(nums[i]) - 1 # 將目標(biāo)位置的數(shù)字標(biāo)記為負(fù)數(shù)表示這個(gè)位置對(duì)應(yīng)的數(shù)字出現(xiàn)過(guò) if nums[correct_pos] 0: nums[correct_pos] -nums[correct_pos] # 第二遍遍歷找出還是正數(shù)的位置 result [] for i in range(n): if nums[i] 0: result.append(i 1) return result這種方法的巧妙之處在于用正負(fù)號(hào)來(lái)標(biāo)記既保留了原始數(shù)字信息又完成了狀態(tài)記錄。4.2 尋找缺失的第一個(gè)正數(shù)LeetCode 41 題要求找出數(shù)組中缺失的最小正整數(shù)。這道題對(duì)原地哈希的要求更高def firstMissingPositive(nums): n len(nums) # 第一遍將每個(gè)正整數(shù)放到正確位置 for i in range(n): while 1 nums[i] n and nums[i] ! nums[nums[i] - 1]: # 交換到正確位置 correct_pos nums[i] - 1 nums[i], nums[correct_pos] nums[correct_pos], nums[i] # 第二遍找出第一個(gè)位置不匹配的 for i in range(n): if nums[i] ! i 1: return i 1 return n 14.3 原地哈希的性能分析原地哈希的時(shí)間復(fù)雜度通常是 O(n)因?yàn)槊總€(gè)數(shù)字最多被交換一次就能到達(dá)正確位置?？臻g復(fù)雜度是 O(1)符合題目要求。但要注意雖然理論上是 O(n)但實(shí)際常數(shù)因子可能比較大因?yàn)樯婕岸啻谓粨Q操作。在數(shù)據(jù)量特別大時(shí)如果對(duì)性能要求極高可能需要考慮其他優(yōu)化。5. 實(shí)戰(zhàn)中的調(diào)試技巧和常見(jiàn)錯(cuò)誤即使理解了算法思路實(shí)際編碼時(shí)還是容易出錯(cuò)。下面是我總結(jié)的幾個(gè)調(diào)試技巧。5.1 使用小樣本測(cè)試不要一上來(lái)就用復(fù)雜的大數(shù)組測(cè)試。先用最簡(jiǎn)單的例子驗(yàn)證# 測(cè)試用例1明顯的重復(fù) test1 [1, 3, 4, 2, 2] # 應(yīng)該返回 2 # 測(cè)試用例2重復(fù)在開(kāi)頭 test2 [3, 1, 3, 4, 2] # 應(yīng)該返回 3 # 測(cè)試用例3重復(fù)在結(jié)尾 test3 [1, 2, 3, 4, 4] # 應(yīng)該返回 45.2 添加詳細(xì)的日志輸出在調(diào)試階段可以添加打印語(yǔ)句來(lái)跟蹤執(zhí)行過(guò)程def findDuplicate_debug(nums): n len(nums) i 0 step 0 while i n: step 1 print(f步驟 {step}: i{i}, nums{nums}) if nums[i] i 1: print(f 數(shù)字 {nums[i]} 已在正確位置i) i 1 continue correct_pos nums[i] - 1 print(f 數(shù)字 {nums[i]} 應(yīng)該在位置 {correct_pos}) if nums[correct_pos] nums[i]: print(f 找到重復(fù)數(shù)字: {nums[i]}) return nums[i] print(f 交換 nums[{i}] 和 nums[{correct_pos}]) nums[i], nums[correct_pos] nums[correct_pos], nums[i] return -15.3 常見(jiàn)錯(cuò)誤類型錯(cuò)誤1索引越界# 錯(cuò)誤沒(méi)有檢查數(shù)字是否在有效范圍內(nèi) correct_pos nums[i] - 1 # 如果 nums[i] 0會(huì)得到 -1索引越界錯(cuò)誤2無(wú)限循環(huán)# 錯(cuò)誤在某種情況下交換后數(shù)字仍不在正確位置但條件判斷有問(wèn)題 while nums[i] ! i 1: # 可能永遠(yuǎn)不滿足條件錯(cuò)誤3修改原數(shù)組影響后續(xù)判斷# 錯(cuò)誤在需要保持原數(shù)組的情況下修改了數(shù)組 # 有些題目要求不能修改原數(shù)組這時(shí)候就不能用原地哈希6. 原地哈希的替代方案比較雖然原地哈希很巧妙但并不是所有情況下都是最佳選擇。了解替代方案有助于在面試中展現(xiàn)全面的思考。6.1 二分查找法對(duì)于找重復(fù)數(shù)字的問(wèn)題還可以用二分查找的思路def findDuplicate_binary_search(nums): left, right 1, len(nums) - 1 while left right: mid (left right) // 2 # 統(tǒng)計(jì)小于等于 mid 的數(shù)字個(gè)數(shù) count 0 for num in nums: if num mid: count 1 # 如果計(jì)數(shù)大于 mid說(shuō)明重復(fù)數(shù)字在左半部分 if count mid: right mid else: left mid 1 return left這種方法的時(shí)間復(fù)雜度是 O(n log n)空間復(fù)雜度 O(1)不修改原數(shù)組。6.2 快慢指針?lè)硪环N巧妙的解法是類比鏈表環(huán)檢測(cè)def findDuplicate_floyd(nums): # 第一階段找到相遇點(diǎn) slow nums[0] fast nums[0] while True: slow nums[slow] fast nums[nums[fast]] if slow fast: break # 第二階段找到環(huán)的入口 slow nums[0] while slow ! fast: slow nums[slow] fast nums[fast] return slow這種方法也是 O(n) 時(shí)間O(1) 空間而且不修改原數(shù)組。6.3 方案選擇建議根據(jù)具體需求選擇方案如果需要保持原數(shù)組不變選擇二分查找或快慢指針如果空間限制嚴(yán)格且允許修改數(shù)組原地哈希是最佳選擇如果數(shù)據(jù)量很大二分查找的常數(shù)因子更小可能更快如果需要找出所有消失的數(shù)字原地哈希的標(biāo)記法最合適7. 從原地哈希學(xué)到的編程思維原地哈希的價(jià)值不僅在于解決具體問(wèn)題更在于它體現(xiàn)了一種重要的編程思維在約束條件下創(chuàng)造性地利用現(xiàn)有資源。7.1 空間換時(shí)間的權(quán)衡在大多數(shù)情況下我們習(xí)慣用空間換時(shí)間比如用哈希表加速查找。但原地哈希反其道而行在空間受限時(shí)通過(guò)更復(fù)雜的邏輯和更多的時(shí)間操作來(lái)解決問(wèn)題。這種思維在嵌入式開(kāi)發(fā)、內(nèi)存敏感的場(chǎng)景中特別有用。7.2 數(shù)組索引的多種用途數(shù)組索引不僅可以表示位置還可以存儲(chǔ)狀態(tài)信息。原地哈希中我們通過(guò)數(shù)字與索引的對(duì)應(yīng)關(guān)系既完成了排序又實(shí)現(xiàn)了查重。類似的思路還可以用在其他問(wèn)題上比如用數(shù)組本身來(lái)記錄訪問(wèn)狀態(tài)、用正負(fù)號(hào)表示布爾值等。7.3 算法模板的靈活應(yīng)用原地哈希的基本模板是遍歷數(shù)組將每個(gè)元素放到它應(yīng)該在的位置在放置過(guò)程中檢查條件重復(fù)、缺失等這個(gè)模板可以靈活調(diào)整來(lái)解決不同變種問(wèn)題。掌握這種元算法比死記硬背具體代碼更有價(jià)值。原地哈希真正考驗(yàn)的是對(duì)數(shù)組操作的深入理解和邊界情況的處理能力。我建議在掌握基本思路后多嘗試不同的變種題目體會(huì)其中的共性和差異。這樣在實(shí)際遇到類似問(wèn)題時(shí)就能快速識(shí)別出適用場(chǎng)景并給出優(yōu)雅的解決方案。