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