前言：本文將介紹隨機(jī)選擇，分治法，減治法的思想，以及TopK問(wèn)題優(yōu)化的來(lái)龍去脈，原理與細(xì)節(jié)，保證有收獲。
面試中，TopK，是問(wèn)得比較多的幾個(gè)問(wèn)題之一，到底有幾種方法，這些方案里蘊(yùn)含的優(yōu)化思路究竟是怎么樣的，今天和大家聊一聊。畫(huà)外音：除非校招，我在面試過(guò)程中從不問(wèn)TopK這個(gè)問(wèn)題。從arr[1, n]這n個(gè)數(shù)中，找出最大的k個(gè)數(shù)，這就是經(jīng)典的TopK問(wèn)題。從arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 這n=12個(gè)數(shù)中，找出最大的k=5個(gè)。排序是最容易想到的方法，將n個(gè)數(shù)排序之后，取出最大的k個(gè)，即為所得。sort(arr, 1, n);
return arr[1, k];
時(shí)間復(fù)雜度：O(n*lg(n))
分析：明明只需要TopK，卻將全局都排序了，這也是這個(gè)方法復(fù)雜度非常高的原因。那能不能不全局排序，而只局部排序呢？這就引出了第二個(gè)優(yōu)化方法。不再全局排序，只對(duì)最大的k個(gè)排序。冒泡是一個(gè)很常見(jiàn)的排序方法，每冒一個(gè)泡，找出最大值，冒k個(gè)泡，就得到TopK。for(i=1 to k){
bubble_find_max(arr,i);
}
return arr[1, k];
分析：冒泡，將全局排序優(yōu)化為了局部排序，非TopK的元素是不需要排序的，節(jié)省了計(jì)算資源。不少朋友會(huì)想到，需求是TopK，是不是這最大的k個(gè)元素也不需要排序呢？這就引出了第三個(gè)優(yōu)化方法。先用前k個(gè)元素生成一個(gè)小頂堆，這個(gè)小頂堆用于存儲(chǔ)，當(dāng)前最大的k個(gè)元素。接著，從第k+1個(gè)元素開(kāi)始掃描，和堆頂（堆中最小的元素）比較，如果被掃描的元素大于堆頂，則替換堆頂?shù)脑兀⒄{(diào)整堆，以保證堆內(nèi)的k個(gè)元素，總是當(dāng)前最大的k個(gè)元素。直到，掃描完所有n-k個(gè)元素，最終堆中的k個(gè)元素，就是猥瑣求的TopK。heap[k] = make_heap(arr[1, k]);
for(i=k+1 to n){
adjust_heap(heep[k],arr[i]);
}
return heap[k];
時(shí)間復(fù)雜度：O(n*lg(k))畫(huà)外音：n個(gè)元素掃一遍，假設(shè)運(yùn)氣很差，每次都入堆調(diào)整，調(diào)整時(shí)間復(fù)雜度為堆的高度，即lg(k)，故整體時(shí)間復(fù)雜度是n*lg(k)。分析：堆，將冒泡的TopK排序優(yōu)化為了TopK不排序，節(jié)省了計(jì)算資源。堆，是求TopK的經(jīng)典算法，那還有沒(méi)有更快的方案呢？隨機(jī)選擇算在是《算法導(dǎo)論》中一個(gè)經(jīng)典的算法，其時(shí)間復(fù)雜度為O(n)，是一個(gè)線性復(fù)雜度的方法。這個(gè)方法并不是所有同學(xué)都知道，為了將算法講透，先聊一些前序知識(shí)，一個(gè)所有程序員都應(yīng)該爛熟于胸的經(jīng)典算法：快速排序。（1）如果有朋友說(shuō)，“不知道快速排序，也不妨礙我寫(xiě)業(yè)務(wù)代碼呀”…額...（2）除非校招，我在面試過(guò)程中從不問(wèn)快速排序，默認(rèn)所有工程師都知道；void quick_sort(int[]arr, int low, inthigh){
if(low== high) return;
int i = partition(arr, low, high);
quick_sort(arr, low, i-1);
quick_sort(arr, i+1, high);
}
分治法（Divide&Conquer），把一個(gè)大的問(wèn)題，轉(zhuǎn)化為若干個(gè)子問(wèn)題（Divide），每個(gè)子問(wèn)題“都”解決，大的問(wèn)題便隨之解決（Conquer）。這里的關(guān)鍵詞是“都”。從偽代碼里可以看到，快速排序遞歸時(shí)，先通過(guò)partition把數(shù)組分隔為兩個(gè)部分，兩個(gè)部分“都”要再次遞歸。減治法（Reduce&Conquer），把一個(gè)大的問(wèn)題，轉(zhuǎn)化為若干個(gè)子問(wèn)題（Reduce），這些子問(wèn)題中“只”解決一個(gè)，大的問(wèn)題便隨之解決（Conquer）。這里的關(guān)鍵詞是“只”。二分查找binary_search，BS，是一個(gè)典型的運(yùn)用減治法思想的算法，其偽代碼是：int BS(int[]arr, int low, inthigh, int target){
if(low> high) return -1;
mid= (low+high)/2;
if(arr[mid]== target) return mid;
if(arr[mid]> target)
return BS(arr, low, mid-1, target);
else
return BS(arr, mid+1, high, target);
}
從偽代碼可以看到，二分查找，一個(gè)大的問(wèn)題，可以用一個(gè)mid元素，分成左半?yún)^(qū)，右半?yún)^(qū)兩個(gè)子問(wèn)題。而左右兩個(gè)子問(wèn)題，只需要解決其中一個(gè)，遞歸一次，就能夠解決二分查找全局的問(wèn)題。通過(guò)分治法與減治法的描述，可以發(fā)現(xiàn)，分治法的復(fù)雜度一般來(lái)說(shuō)是大于減治法的：i = partition(arr, low, high);顧名思義，partition會(huì)把整體分為兩個(gè)部分。更具體的，會(huì)用數(shù)組arr中的一個(gè)元素（默認(rèn)是第一個(gè)元素t=arr[low]）為劃分依據(jù)，將數(shù)據(jù)arr[low, high]劃分成左右兩個(gè)子數(shù)組：以上述TopK的數(shù)組為例，先用第一個(gè)元素t=arr[low]為劃分依據(jù)，掃描一遍數(shù)組，把數(shù)組分成了兩個(gè)半?yún)^(qū)：很容易知道，partition的時(shí)間復(fù)雜度是O(n)。畫(huà)外音：把整個(gè)數(shù)組掃一遍，比t大的放左邊，比t小的放右邊，最后t放在中間N[i]。partition和TopK問(wèn)題有什么關(guān)系呢？TopK是希望求出arr[1,n]中最大的k個(gè)數(shù)，那如果找到了第k大的數(shù)，做一次partition，不就一次性找到最大的k個(gè)數(shù)了么？畫(huà)外音：即partition后左半?yún)^(qū)的k個(gè)數(shù)。問(wèn)題變成了arr[1, n]中找到第k大的數(shù)。再回過(guò)頭來(lái)看看第一次partition，劃分之后：i = partition(arr, 1, n);（1）如果i大于k，則說(shuō)明arr[i]左邊的元素都大于k，于是只遞歸arr[1, i-1]里第k大的元素即可；（2）如果i小于k，則說(shuō)明說(shuō)明第k大的元素在arr[i]的右邊，于是只遞歸arr[i+1, n]里第k-i大的元素即可；這就是隨機(jī)選擇算法randomized_select，RS，其偽代碼如下：int RS(arr, low, high, k){
if(low== high) return arr[low];
i= partition(arr, low, high);
t = i-low; //數(shù)組前半部分元素個(gè)數(shù)
if(t>=k)
return RS(arr, low, i-1, k); //求前半部分第k大
else
return RS(arr, i+1, high, k-t); //求后半部分第k-t大
}
這是一個(gè)典型的減治算法，遞歸內(nèi)的兩個(gè)分支，最終只會(huì)執(zhí)行一個(gè)，它的時(shí)間復(fù)雜度是O(n)。（1）分治法，大問(wèn)題分解為小問(wèn)題，小問(wèn)題都要遞歸各個(gè)分支，例如：快速排序；（2）減治法，大問(wèn)題分解為小問(wèn)題，小問(wèn)題只要遞歸一個(gè)分支，例如：二分查找，隨機(jī)選擇；通過(guò)隨機(jī)選擇（randomized_select），找到arr[1, n]中第k大的數(shù)，再進(jìn)行一次partition，就能得到TopK的結(jié)果。TopK，不難；其思路優(yōu)化過(guò)程，不簡(jiǎn)單：（2）局部排序，只排序TopK個(gè)數(shù)，O(n*k)；（3）堆，TopK個(gè)數(shù)也不排序了，O(n*lg(k))；（4）分治法，每個(gè)分支“都要”遞歸，例如：快速排序，O(n*lg(n))；（5）減治法，“只要”遞歸一個(gè)分支，例如：二分查找O(lg(n))，隨機(jī)選擇O(n)；（6）TopK的另一個(gè)解法：隨機(jī)選擇+partition；希望大家對(duì)TopK有新的認(rèn)識(shí)，謝轉(zhuǎn)。架構(gòu)師之路-分享可落地的架構(gòu)文章TopK，還有沒(méi)有更快的方法，且聽(tīng)下回分解。
