LeetCode 熱題100里有一道幾乎每個 Java 后端候選人都繞不開的題數(shù)組中的第K個最大元素。我第一次在面試現(xiàn)場被問到它時第一反應(yīng)是Arrays.sort之后取倒數(shù)第 k 個結(jié)果被面試官一連串“時間復(fù)雜度能優(yōu)化嗎數(shù)據(jù)流場景怎么辦”給問住了。后來我把這道題的兩個標準解法——堆排序和快速選擇——徹底吃透才發(fā)現(xiàn)它其實是一把打開 TopK 問題大門的鑰匙。這篇文章會把兩道解法的原理、Java 實現(xiàn)、復(fù)雜度推導(dǎo)以及我實際調(diào)試中踩過的坑完整拆開適合準備 LeetCode 刷題、Java 面試八股文以及想搞懂“第 K 大/小元素”這類題通用套路的讀者。1. 先把題目嚼碎這題到底在考什么1.1 題目要義與目標索引換算先看題目本身給定一個整數(shù)數(shù)組nums和一個整數(shù)k返回數(shù)組中第 k 個最大的元素。注意這里說的是“第 k 個最大的元素”不是“第 k 個不同的元素”。也就是說數(shù)組里有重復(fù)值時重復(fù)值也要參與排序計數(shù)。舉個例子nums [3,2,1,5,6,4], k 2排序后是[1,2,3,4,5,6]第 2 大元素是 5。如果數(shù)組里有重復(fù)值比如[2,2,3,1], k 2排序后是[1,2,2,3]第 2 大元素是 2而不是 3。這里新手最容易踩的第一個坑是“第 k 大”和“數(shù)組索引”之間的換算。數(shù)組升序排序后最小的元素在索引 0最大的元素在索引n-1。所以第 1 大對應(yīng)索引n-1第 2 大對應(yīng)索引n-2第 k 大就對應(yīng)索引n-k。換算成代碼就是int target nums.length - k;這個target代表“在升序排列中目標元素所在的索引位置”。后面快速選擇解法會頻繁用到它理解這個換算比背代碼重要得多。我見過不少人在面試時直接寫int target k那是在按第 k 小處理結(jié)果邊界全錯一調(diào)試就露餡。1.2 三條出路排序、堆、快速選擇圍繞這道題通常有三條技術(shù)路線方案時間復(fù)雜度空間復(fù)雜度特點全排序后取值O(n log n)O(1)最好寫但面試會被追問優(yōu)化大小為 k 的小頂堆O(n log k)O(k)適合海量數(shù)據(jù)流k 小時很香快速選擇算法平均 O(n)最壞 O(n2)迭代 O(1)平均最快是典型減治思想全排序的思路一句話就能說清Arrays.sort(nums)之后返回nums[n-k]。Java 的Arrays.sort對基本類型數(shù)組用的是 Dual-Pivot QuickSort對對象數(shù)組用的是 TimSort性能已經(jīng)很好了。但面試官出這道題從來不是想聽你調(diào)庫而是想看你能不能意識到“找第 k 大根本不需要把整個數(shù)組排好序”。這就是后面兩種解法的出發(fā)點。為什么標題鎖定堆排序和快速選擇因為這兩個方案分別代表了 TopK 問題里最典型的兩類解法一類是用堆維護“最大的 k 個數(shù)”適合流式數(shù)據(jù)和海量數(shù)據(jù)另一類是用 partition 分區(qū)思想做減治平均復(fù)雜度能壓到 O(n)。把這兩條路走通遇到前 K 個高頻元素、最接近原點的 K 個點、數(shù)據(jù)流中的第 K 大元素這類變體題都能直接套。1.3 另一條小眾路線計數(shù)排序/桶排序如果題目額外限制了數(shù)據(jù)范圍比如數(shù)組里所有元素都在[0, 10000]之間那還可以用計數(shù)排序或桶排序。計數(shù)排序的思路是開一個長度為maxValue - minValue 1的計數(shù)數(shù)組統(tǒng)計每個值出現(xiàn)次數(shù)然后從大到小累加計數(shù)累加到 k 時對應(yīng)元素就是答案。這種方案的時間復(fù)雜度是 O(n range)當 range 遠大于 n 時反而更慢。而且它要求數(shù)據(jù)必須是整數(shù)、范圍可枚舉。LeetCode 原題的數(shù)據(jù)范圍是-10^4 nums[i] 10^4其實用桶排序也能過但面試官通常希望你先掌握通用解法再提特殊解作為補充而不是上來就開桶。2. 小頂堆解法用堆維護“最大的k個數(shù)”2.1 為什么偏要用小頂堆而不是大頂堆這是這道題最經(jīng)典的一個概念陷阱。很多人一聽“找第 k 大”第一反應(yīng)是“那我要維護一個大頂堆每次把最大的彈出來”。方向反了。我們換個角度想維護一個大小為 k 的小頂堆堆里裝的是“當前已經(jīng)遍歷過的元素中最大的 k 個”。因為小頂堆的堆頂是堆里最小的元素所以這個堆頂天然就是“最大的 k 個元素里的最小值”也就是第 k 大的元素。每遍歷一個新元素時只需要和堆頂比較如果新元素比堆頂大說明它值得進入“前 k 大陣營”那就把堆頂彈出把它放進去如果新元素比堆頂小或相等說明它連當前第 k 大都擠不掉直接忽略。這里我給一個非常直觀的模擬。假設(shè)k 3數(shù)組依次是[5, 1, 9, 2, 8]遇到 5堆不滿直接放入堆為[5]遇到 1堆不滿直接放入堆為[1, 5]遇到 9堆不滿直接放入堆為[1, 5, 9]遇到 2堆已滿2 堆頂 1彈出 1放入 2堆為[2, 5, 9]遇到 8堆已滿8 堆頂 2彈出 2放入 8堆為[5, 8, 9]最后堆頂是 5也就是數(shù)組中最大的三個數(shù) 5、8、9 里最小的那個恰好是第 3 大元素。這個模擬跑完小頂堆的原因就一目了然了用一個能 O(1) 拿到最小值的結(jié)構(gòu)來維護候選集合誰最“菜”誰就先出局。2.2 Java 實現(xiàn)與逐行拆解Java 里實現(xiàn)堆最直接的方式是PriorityQueue默認是小頂堆。完整代碼如下public int findKthLargest(int[] nums, int k) { // 默認是小頂堆堆頂永遠是最小值 PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { // 堆還沒滿直接塞進去 if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { // 當前元素比堆頂大說明它有資格進入前 k 大 minHeap.poll(); minHeap.offer(num); } // 如果 num 堆頂說明它不是前 k 大直接跳過 } // 堆頂就是最大的 k 個元素里最小的那個即第 k 大 return minHeap.peek(); }這里有幾個細節(jié)值得單獨拿出來說。第一new PriorityQueue(k)里的k只是初始容量不是“最大容量”。Java 的PriorityQueue不會因為你傳入k就自動只保留 k 個元素它會根據(jù)元素數(shù)量自動擴容。所以代碼里必須手動控制size這是新手常犯的錯我在面試時見過好幾個人在這里翻車。第二peek()和poll()的時間復(fù)雜度是 O(1)offer()的時間復(fù)雜度是 O(log k)。上面的寫法先判斷num minHeap.peek()再執(zhí)行poll()和offer()避免了無意義的堆操作。如果寫的是“先 offer 再判斷 size 是否超 k超了就 poll”雖然結(jié)果一樣但每次都會多做一次 O(log k) 的堆化數(shù)據(jù)量大了差距明顯。第三PriorityQueueInteger是對象類型對int[]數(shù)組需要逐個裝箱。Java 的自動裝箱會有一定開銷但在這道題的量級下完全不是問題。如果你追求極致性能可以自己用數(shù)組實現(xiàn)一個二叉堆把比較邏輯內(nèi)聯(lián)不過面試筆試里完全沒必要。2.3 堆解法的復(fù)雜度賬怎么算時間上每個元素最多經(jīng)歷一次offer()在堆滿后可能還會多一次poll()。PriorityQueue的插入和刪除都是 O(log k)n 個元素整體就是 O(n log k)。注意不是 O(n log n)因為我們始終把堆的規(guī)模限制在 k 以內(nèi)?？臻g上堆里最多存 k 個元素所以是 O(k)。如果 k 很小比如 k 10堆的規(guī)模就很小內(nèi)存開銷非常低這正是堆解法在“海量數(shù)據(jù) TopK”場景下的核心優(yōu)勢你不需要把所有數(shù)據(jù)一次性加載到內(nèi)存只要維護一個容量為 k 的小頂堆就能在 O(n log k) 的時間里得到答案。數(shù)據(jù)流源源不斷來的時候堆解法也能在線處理新來一個元素就更新一次堆。反過來當 k 接近 n 時堆解法就沒什么優(yōu)勢了。比如 k n/2那堆的規(guī)模是 n/2復(fù)雜度退化到 O(n log n)和直接全排序差不多還多堆內(nèi)存開銷。這時候快速選擇或者全排序反而更合適。所以面試中如果被問到“k 很大時你怎么辦”不能只背一個堆解法。3. 快速選擇解法快排思想減一半工作量3.1 快速排序與快速選擇的血緣關(guān)系快速選擇的核心是分區(qū)partition而分區(qū)正是快速排序的靈魂。理解了這個關(guān)系就理解了為什么快速選擇平均能到 O(n)。快速排序每一輪會選一個 pivot把數(shù)組分成兩部分左邊都小于等于 pivot右邊都大于等于 pivot。關(guān)鍵事實是分區(qū)結(jié)束后pivot 已經(jīng)落在它最終的位置上也就是說它左邊的元素數(shù)量是固定的它在整個數(shù)組升序排列中的最終索引就是分區(qū)返回的下標?？焖龠x擇利用了這一點我們不需要排序整個數(shù)組只需要找到目標索引target n - k。每次分區(qū)后拿返回的下標p跟target比較p targetpivot 就是這個位置直接返回nums[p]p target目標在右半?yún)^(qū)丟棄左半?yún)^(qū)繼續(xù)在右半?yún)^(qū)找p target目標在左半?yún)^(qū)丟棄右半?yún)^(qū)繼續(xù)在左半?yún)^(qū)找因為每輪只需要處理一側(cè)工作量從快速排序的“兩個子區(qū)間都處理”變成了“只處理一個子區(qū)間”這就是減治思想?？焖倥判驈?fù)雜度是 O(n log n)快速選擇平均降到 O(n)本質(zhì)原因就在這里。換個更直白的說法快速排序像是一個老師要把全班 50 個人的成績都排好名次每個環(huán)節(jié)都要比較所有分區(qū)快速選擇只是想知道第 10 名是誰每次分區(qū)后只要盯著一半?yún)^(qū)域繼續(xù)找就行另一半直接扔掉。3.2 分區(qū)函數(shù)的三種寫法和取舍分區(qū)函數(shù)partition是快速選擇的基石寫不好整個算法就會出各種邊界問題。常見的寫法有三種Lomuto 分區(qū)、Hoare 分區(qū)、三數(shù)取中/隨機化增強。Lomuto 分區(qū)思路最簡單選最右邊的元素作為 pivot用一個i指針記錄“小于等于 pivot 的區(qū)域邊界”從左到右掃描遇到小于等于 pivot 的元素就把它換到i位置然后i。掃描結(jié)束后把 pivot 換到i位置返回i。它的交換次數(shù)比 Hoare 多但代碼不容易寫錯是面試首選。Hoare 分區(qū)是左右雙指針left從左往右找大于 pivot 的元素right從右往左找小于 pivot 的元素找到后交換。它平均交換次數(shù)少但循環(huán)條件和指針移動的細節(jié)很多稍不小心就會死循環(huán)或越界。比如兩個指針相遇時下標怎么處理、重復(fù)元素會不會導(dǎo)致無限交換這些問題在緊張狀態(tài)下很容易寫亂。三數(shù)取中和隨機化不是分區(qū)邏輯本身而是對“選哪個元素當 pivot”的改進。普通 Lomuto 固定選最右元素如果數(shù)組本身是近乎有序的分區(qū)會嚴重不平衡。三數(shù)取中是從left、mid、right三個位置取中間值當 pivot大概率能讓分區(qū)均勻一些隨機化則是隨機選一個下標當 pivot從概率上避免人為構(gòu)造的最壞輸入。兩者都只是調(diào)整 pivot 的選法不改變分區(qū)主體代碼。3.3 迭代實現(xiàn)第K大元素完整 Java 代碼先看完整實現(xiàn)我下面逐段解釋public int findKthLargest(int[] nums, int k) { int n nums.length; int target n - k; // 第 k 大元素在升序排列中的索引 int left 0; int right n - 1; while (true) { int p partition(nums, left, right); if (p target) { return nums[p]; } else if (p target) { left p 1; } else { right p - 1; } } } private int partition(int[] nums, int left, int right) { // 三數(shù)取中讓 nums[left] nums[mid] nums[right] int mid left (right - left) / 2; if (nums[left] nums[mid]) swap(nums, left, mid); if (nums[left] nums[right]) swap(nums, left, right); if (nums[mid] nums[right]) swap(nums, mid, right); // 把中位數(shù)換到最右端作為 pivot swap(nums, mid, right); int pivot nums[right]; // Lomuto 分區(qū) int i left; for (int j left; j right; j) { if (nums[j] pivot) { swap(nums, i, j); i; } } // 把 pivot 放回正確位置 swap(nums, i, right); return i; } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }這里最需要注意的地方是while (true)循環(huán)。為什么用死循環(huán)而不是while (left right)因為每次分區(qū)后p一定落在[left, right]范圍內(nèi)并且只要p ! target我們就會縮小搜索區(qū)間區(qū)間長度嚴格遞減最終一定會出現(xiàn)p target。所以死循環(huán)是安全的不會無限循環(huán)。當然用while (left right)并在循環(huán)外返回nums[left]也可以但死循環(huán)配合立即返回更直觀。partition內(nèi)部的i是“小于等于 pivot 的區(qū)域邊界”初始是left。掃描時如果nums[j] pivot就把nums[j]換到i位置并讓i自增。掃描結(jié)束后[left, i-1]都是小于等于 pivot 的元素[i, right-1]都是大于 pivot 的元素最后把最右側(cè)的 pivot 換到i就完成了整個分區(qū)。這里nums[j] pivot用的是小于等于。如果改成嚴格小于會讓等于 pivot 的元素全部歸到右側(cè)在大量重復(fù)元素時可能導(dǎo)致分區(qū)不均衡。后面講三路分區(qū)時我會更詳細展開。3.4 期望復(fù)雜度推導(dǎo)為什么平均是 O(n)快速選擇平均 O(n) 的推導(dǎo)不復(fù)雜。假設(shè)每次分區(qū)都能把區(qū)間差不多分成兩半那么處理規(guī)模為 n 的問題時先做 O(n) 的分區(qū)然后只需要繼續(xù)處理規(guī)模大約為 n/2 的其中一個子區(qū)間于是T(n) T(n/2) O(n)展開是T(n) O(n) O(n/2) O(n/4) ... O(2n) O(n)等比級數(shù)求和的結(jié)果是 2n所以是線性復(fù)雜度。這里的關(guān)鍵是“每輪只處理一側(cè)”如果處理兩側(cè)那就是快速排序的 O(n log n) 了。最壞情況發(fā)生在每次分區(qū)都極度不平衡的時候。比如數(shù)組已經(jīng)升序排列pivot 又固定選最右側(cè)元素那每次分區(qū)后左邊區(qū)間有 n-1 個元素右邊為空目標每輪只減少一個元素。此時 T(n) T(n-1) O(n) O(n2)和冒泡排序一樣慢。所以工程實現(xiàn)里必須引入隨機化或三數(shù)取中。隨機化能保證在概率意義上很難碰到最壞輸入三數(shù)取中則讓“近乎有序”這類常見數(shù)據(jù)也不容易退化。兩者可以結(jié)合比如分區(qū)前先做三數(shù)取中再隨機挑一個。不過 LeetCode 場景下三數(shù)取中已經(jīng)足夠安全。4. 復(fù)雜度對照與面試選型指南4.1 五種方案的完整對照面試時經(jīng)常要求你說清楚每種方案的差異我用一張表整理方案時間復(fù)雜度空間復(fù)雜度適用場景關(guān)鍵優(yōu)缺點全排序O(n log n)O(1)數(shù)據(jù)量小或不追求最優(yōu)最穩(wěn)妥但面試會被追問小頂堆大小 kO(n log k)O(k)數(shù)據(jù)流、海量數(shù)據(jù)、k 較小內(nèi)存可控但 k 大時退化大頂堆全量O(n k log n)O(n)k 很小且數(shù)據(jù)能一次性裝入需要全量建堆內(nèi)存 O(n)快速選擇平均平均 O(n)最壞 O(n2)迭代 O(1)單次查詢、數(shù)組可改造平均最快最壞需隨機化防御計數(shù)/桶排序O(n range)O(range)整數(shù)且數(shù)據(jù)范圍有限范圍大時不適用我補充一個細節(jié)大頂堆全量方案是指先把所有元素放進一個大頂堆堆頂是最大值然后連續(xù)poll()k-1 次堆頂就是第 k 大。構(gòu)建大頂堆的時間是 O(n)poll 一次是 O(log n)整體 O(n k log n)。它能處理 k 特別小的情況但因為需要存下整個數(shù)組空間上并不占優(yōu)工程里很少有人用它替代“大小 k 的小頂堆”。4.2 什么數(shù)據(jù)會讓快速選擇翻車快速選擇最怕“刻意構(gòu)造的輸入”。經(jīng)典反例是數(shù)組幾乎有序pivot 固定取最右側(cè)元素每次分區(qū)后另一個子區(qū)間都接近空算法退化到 O(n2)。LeetCode 的測試數(shù)據(jù)一般不會故意惡心你但如果你用固定 pivot 的寫法去跑大數(shù)據(jù)量、幾乎有序的用例超時是有可能的。另一個容易翻車的情況是數(shù)組里全部是相同元素。Lomuto 分區(qū)如果寫成nums[j] pivot會把等于 pivot 的元素都放到右側(cè)分區(qū)后左邊為空右邊 n-1 個元素同樣退化。解決方法是把比較改成或者直接上三路分區(qū)。我在本地跑過[1,1,1,...,1]這種數(shù)據(jù)三路分區(qū)一次就能定位普通 Lomuto 分區(qū)用嚴格小于會退化得很明顯。還有個不太起眼但實際存在的問題遞歸深度。如果遞歸實現(xiàn)快速選擇每次只處理一側(cè)理論上遞歸深度可能達到 n極端數(shù)據(jù)下會棧溢出。LeetCode 的評測環(huán)境棧很深一般不會爆但如果是自己公司的算法面試現(xiàn)場手寫遞歸被問到“棧溢出怎么辦”就很尷尬。所以我的建議是直接寫迭代版本這是工程上更穩(wěn)妥的選擇。4.3 面試官追問時怎么答這題在面試里幾乎必然是連環(huán)追問的。我把我被問過的問題和合理答法整理了一下。問“時間復(fù)雜度是多少能不能證明”這是送分題答平均 O(n)展開等比級數(shù)求和然后主動補一句最壞 O(n2)再說我用了三數(shù)取中/隨機化來避免最壞情況。整套回答行云流水比只說“平均O(n)”好太多。問“這個算法能處理數(shù)據(jù)流嗎”不能?？焖龠x擇必須拿到全量數(shù)組才能做分區(qū)數(shù)據(jù)流場景應(yīng)該用小頂堆堆里維護最大的 k 個新元素來了實時更新。這道題在“大數(shù)據(jù)面試題”里經(jīng)常和海量數(shù)據(jù)處理一起出現(xiàn)堆解法是那一類問題的標準答案。問“如果 k1 或 kn 呢”快速選擇只需要一次分區(qū)就能找到答案堆要遍歷完整個數(shù)組才能確定堆頂。單次查詢場景下快速選擇更優(yōu)。但如果是持續(xù)查詢比如“不斷有新元素進來隨時問當前第 k 大”那只能靠堆。問“內(nèi)存裝不下整個數(shù)組怎么辦”那就不能全排序也不能快速選擇只能分批處理維護一個大小為 k 的小頂堆從磁盤一部分一部分讀數(shù)據(jù)更新堆。這其實就是海量 TopK 的標準解法。5. 工程化細節(jié)把解法磨成生產(chǎn)級代碼5.1 隨機化 pivot一句話消滅最壞輸入三數(shù)取中能應(yīng)對“近似有序”的數(shù)據(jù)但嚴格來說它仍然是一種固定策略如果攻擊者知道你的取法還是可能構(gòu)造出壞數(shù)據(jù)。最穩(wěn)妥的做法是隨機化int randomIndex left ThreadLocalRandom.current().nextInt(right - left 1); swap(nums, randomIndex, right);ThreadLocalRandom是 Java 并發(fā)包里的工具在當前線程內(nèi)生成隨機數(shù)比new Random()的開銷更低。代碼放在partition的最前面選中隨機下標后把它和right位置的元素交換后續(xù)走 Lomuto 分區(qū)的邏輯完全不用改。隨機化解決的是“策略被預(yù)測”的問題。因為每次選 pivot 的位置是隨機的理論上任何輸入被分到極不平衡兩側(cè)的概率都極低最壞情況只能靠“運氣特別差”才會出現(xiàn)。在線判題環(huán)境里隨機化算法依然能保證正確性只是運行時間可能會有微小波動。我可以給出一個實測經(jīng)驗固定 pivot 的快速選擇在 LeetCode 的 215 題上跑大數(shù)據(jù)量時偶有超時風(fēng)險加上隨機化后基本都能穩(wěn)過。如果你的代碼在本地沒問題但提交超時優(yōu)先檢查 pivot 選法。5.2 重復(fù)元素與三路分區(qū)當數(shù)組里重復(fù)元素很多時普通 Lomuto 分區(qū)的問題在于等于 pivot 的元素會被隨機分配到左右兩側(cè)導(dǎo)致分區(qū)結(jié)果不穩(wěn)定。一種更強悍的做法是荷蘭國旗三路分區(qū)把數(shù)組一次性分成三段小于 pivot、等于 pivot、大于 pivot。這樣等于 pivot 的一整塊可以在一步內(nèi)確定位置不需要再參與后續(xù)遞歸。核心思路是用三個指針lt、i、gtprivate int[] partitionThreeWay(int[] nums, int left, int right, int pivot) { int lt left, i left, gt right; while (i gt) { if (nums[i] pivot) { swap(nums, lt, i); } else if (nums[i] pivot) { swap(nums, i, gt--); } else { i; } } // 返回等于 pivot 的區(qū)間 [lt, gt] return new int[]{lt, gt}; }如果目標索引target落在[lt, gt]區(qū)間內(nèi)直接返回pivot即可。如果target lt只需要處理左段如果target gt處理右段。對于全數(shù)組都是同一個值的極端情況三路分區(qū)一次就結(jié)束時間復(fù)雜度 O(n)。不過這道題用不用三路分區(qū)要看情況。LeetCode 的測試數(shù)據(jù)里重復(fù)元素比例不高普通 Lomuto 加三數(shù)取中完全夠用。但如果面試官特意問“數(shù)組里全是重復(fù)元素怎么辦”三路分區(qū)就是很漂亮的加分答法。我建議兩者都掌握寫代碼時優(yōu)先用三路分區(qū)思路邊界更不容易錯。5.3 邊界保護和健壯性細節(jié)有幾個實現(xiàn)細節(jié)看起來小實際出問題概率很高我單獨列出來。第一中間下標計算一定要寫成left (right - left) / 2不要寫成(left right) / 2。雖然這兩個表達式在大多數(shù)情況下結(jié)果一樣但當left right超過 int 最大值時會溢出結(jié)果變成負數(shù)導(dǎo)致數(shù)組越界。這道題 n 一般不大但養(yǎng)成這個習(xí)慣很重要。第二swap操作要讓兩個下標不相等時才執(zhí)行或者直接交換也無所謂。交換時如果i j純屬白做一次但對性能影響極小。真正需要注意的是 Lomuto 循環(huán)里swap(nums, i, j)的i和j可能相等如果你在swap里用了臨時變量這種自交換沒有任何問題。第三快速選擇是原地修改數(shù)組的。如果你不希望原數(shù)組被破壞需要先nums.clone()再操作。刷題時直接修改原數(shù)組沒問題但真實業(yè)務(wù)代碼里對外提供的 API 最好別改調(diào)用方的數(shù)組否則會有隱蔽的副作用。第四k的邊界。k 1時target n-1處理的始終是最大值k n時target 0處理的是最小值。這兩個邊界在快速選擇里都能自然收斂。堆解法在k 1時堆里始終只保留當前最大值邏輯也正確。6. 踩坑實錄與同類題擴展6.1 我實際踩過的幾個坑第一個坑把PriorityQueue當成“自動限制容量為 k”的容器。我第一次寫堆解法時天真地以為new PriorityQueue(k)會自動只保留 k 個元素結(jié)果堆里越長越大返回的堆頂根本不是第 k 大。后來意識到必須手動判斷 size這個錯誤才徹底改掉。第二個坑快速選擇的 target 換算寫反。我把“第 k 大”誤寫成“第 k 小”target k - 1然后用升序 partition 去找結(jié)果測試用例全錯。排查了很久才發(fā)現(xiàn)問題出在這一行。后來我每次寫這題第一行都先注釋// target n - k因為升序數(shù)組里第 k 大在索引 n-k。聽起來很傻但真的能救命。第三個坑Lomuto 分區(qū)寫成了嚴格小于。nums[j] pivot在大多數(shù)用例下也能跑對但遇到大量重復(fù)元素時退化成 O(n2)。有一次我拿著這段代碼去跑一個全為 1 的 10 萬長度數(shù)組跑了半天沒結(jié)束。改成之后瞬間出結(jié)果。這讓我養(yǎng)成了一個習(xí)慣每次寫完快速選擇本地先壓測三組數(shù)據(jù)隨機數(shù)組、近乎有序數(shù)組、全相同數(shù)組。第四個坑while (true)循環(huán)里返回點寫錯。我早期的代碼是在partition返回后直接return nums[p]但忘了判斷p是否等于target結(jié)果很多時候返回的只是一個隨機 pivot 值問題表現(xiàn)非常詭異。后來我強制自己在循環(huán)里只做兩件事比較p和target更新left/right其他一律不寫邏輯就清晰了。6.2 從這題延伸出去的一串 LeetCode 熱題這道題最厲害的地方是它連通了一大片 TopK 類問題屬于熱題100里的“樞紐題”。我建議刷完它之后馬上做下面這幾道能明顯感覺到套路復(fù)用數(shù)據(jù)流中的第 K 大元素小頂堆解法的直接應(yīng)用維護大小為 k 的堆每個新元素進來都更新堆返回堆頂。這題和 215 幾乎一個模子。前 K 個高頻元素先用哈希表統(tǒng)計頻率再用大小為 k 的小頂堆按頻率排序。核心還是“維護一個容量為 k 的候選集合”。最接近原點的 K 個點把距離算出來放進堆里堆大小 k按距離比較。本質(zhì)依然是 TopK。根據(jù)字符出現(xiàn)頻率排序哈希統(tǒng)計加桶排序或堆排序重點練“統(tǒng)計排序”組合。另外熱題100里的 994 腐爛的橘子、073 愛吃香蕉的狒狒、224 基本計算器這些題雖然解法不同但它們在“細節(jié)邊界多”這一點上和 215 很像。刷 215 時你會養(yǎng)成一個習(xí)慣反復(fù)驗證索引邊界、處理重復(fù)值、考慮最壞數(shù)據(jù)這個習(xí)慣遷移到 BFS 和棧模擬的題目里同樣有用。我個人在實際刷題和面試復(fù)盤中的體會是TopK 題先問自己三個問題——k 有多大數(shù)據(jù)能一次性放內(nèi)存嗎數(shù)據(jù)有沒有大量重復(fù)把這三個問題想清楚用堆還是用快速選擇其實馬上就能判斷。還有一點不要只背代碼要在本地把數(shù)組改成幾乎有序、全相同、含負數(shù)等邊界情況分別跑一遍很多隱藏問題只有在這種壓測下才會暴露。這道題刷透之后你會發(fā)現(xiàn)自己在處理“海量數(shù)據(jù)第 K 大”類問題時思路會清晰很多。