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