前言
在一個(gè)數(shù)組中求其第k大或者第k小的數(shù)的問(wèn)題(其實(shí)就是找按降序或升序排好序的數(shù)組的下標(biāo)為k-1的元素)呜魄，簡(jiǎn)稱TOP-K問(wèn)題。解決TOP-K問(wèn)題最有效的算法是bfprt算法构韵，又稱中位數(shù)的中位數(shù)算法周蹭，該算法由Blum、Floyd疲恢、Pratt凶朗、Rivest、Tarjan提出冈闭。
類似題目 215. 數(shù)組中的第K個(gè)最大元素
bfprt算法
- TOP-K問(wèn)題其實(shí)可以使用快排的
partition來(lái)求解俱尼，通常選擇開(kāi)頭、末尾或隨機(jī)選擇一個(gè)數(shù)作為軸來(lái)劃分?jǐn)?shù)據(jù)萎攒，但這存在一個(gè)問(wèn)題就是最差情況下遇八，算法時(shí)間復(fù)雜度會(huì)退化為。
- 而bfprt算法就是基于
partition的基礎(chǔ)上做出優(yōu)化耍休，旨在選擇一個(gè)合適的樞軸刃永，使得算法的最壞時(shí)間復(fù)雜度為。
bfprt算法的步驟：
- 選擇樞軸
- partition羊精，劃分?jǐn)?shù)據(jù)
- 根據(jù)partition的結(jié)果斯够，遞歸
樞軸的選擇
- 首先將給定數(shù)組劃分為
n / 5組，每組5個(gè)元素喧锦，若有多出不足5個(gè)的读规，自成一組 - 使用插入排序找到每個(gè)組的中位數(shù)，組成中位數(shù)數(shù)組
medians - 找到中位數(shù)數(shù)組
medians中的中位數(shù)燃少，以此作為樞軸去partition
//排序束亏，然后返回中位數(shù)
private int getMedian(int[] nums, int begin, int end){
for(int i = begin + 1;i <= end;i++){
for(int j = i;j > begin && nums[j] < nums[j - 1]; j--){
swap(nums, j ,j - 1);
}
}
return nums[begin + ((end - begin) >> 1)];
}
private int getMedianOfMedians(int[] nums, int begin, int end){
int num = end - begin + 1;
int offset = num % 5 == 0 ? 0 : 1;
int[] medians = new int[num / 5 + offset];
for(int i = 0; i < medians.length;i++){
int subBegin = begin + i * 5;
int subEnd = subBegin + 4;
medians[i] = getMedian(nums, subBegin, Math.min(subEnd, end));
}
//調(diào)用bfprt方法找到medians的中位數(shù)
return bfprt(medians, 0, medians.length - 1, medians.length / 2);
}
partition
-
partition是以某個(gè)元素(假設(shè)為pivot)為樞軸去劃分?jǐn)?shù)組，有兩種劃分方式(以從小到大為例)：-
劃分為三部分(每次確定一個(gè)元素位置)
-
劃分為三部分(荷蘭國(guó)旗問(wèn)題)
-
一輪partition結(jié)束后阵具，pivot就確定了它在數(shù)組中的位置碍遍。
private int[] partition(int[] nums, int begin, int end, int pivot){
int l = begin - 1, r = end + 1;
int i = begin;
while(i < r){
if(nums[i] == pivot){
i++;
}else if(nums[i] > pivot){
swap(nums, ++l, i++);
}else{
swap(nums, i, --r);
}
}
return new int[]{l + 1, r - 1};
}
bfprt求解
bfprt算法采用分治的思想，首先找到樞軸阳液，再partition怕敬，以荷蘭國(guó)旗問(wèn)題的partition為例，它返回中間部分的劃分點(diǎn)[l, r]帘皿，如下圖
因?yàn)橄聵?biāo)
4 -> 6這部分元素的最終位置已經(jīng)確定东跪，所以我們只需要判斷k是否落在這個(gè)區(qū)間，如果是則返回nums[k]鹰溜；如果k < l越庇，說(shuō)明k在左邊部分，則在l的左邊部分繼續(xù)找奉狈；如果k > r卤唉，說(shuō)明k在右邊部分，則在r的右邊部分繼續(xù)找仁期。
private int bfprt(int[] nums, int begin, int end, int k){
if(begin == end) return nums[begin];
int pivot = getMedianOfMedians(nums, begin, end);
int[] partition = partition(nums, begin, end, pivot);
if(k >= partition[0] && k <= partition[1]){
return nums[k];
}else if(k > partition[1]){
return bfprt(nums, partition[1] + 1, end, k);
}else{
return bfprt(nums, begin, partition[0] - 1, k);
}
}
時(shí)間復(fù)雜度
- 每個(gè)組的5個(gè)元素排序時(shí)間復(fù)雜度為
O(1)桑驱，n / 5組一共就是O(n) - 取出中位數(shù)組成中位數(shù)數(shù)組
O(n) - 找到中位數(shù)數(shù)組中的中位數(shù)
T(n / 5) - 左右劃分后，會(huì)折掉一部分?jǐn)?shù)據(jù)跛蛋，最壞情況是
T(7n / 10)
medians數(shù)組的大小為n / 5熬的，那么medians數(shù)組中有n / 10個(gè)數(shù)比中位數(shù)pivot小，而這n / 10個(gè)數(shù)在自己的組內(nèi)又有兩個(gè)數(shù)比它小赊级，所以至少有3n / 10個(gè)數(shù)比pivot小押框，所以最多有7n / 10個(gè)數(shù)比pivot大。
最后T(n) = T(7n / 10) + T(n / 5) + O(n)理逊，得到時(shí)間復(fù)雜度為O(n)
總結(jié)
- 隨機(jī)選擇樞軸時(shí)橡伞，會(huì)導(dǎo)致一個(gè)不好的情況是
partition之后盒揉，折掉的數(shù)據(jù)很少，剩下一部分?jǐn)?shù)據(jù)繼續(xù)遞歸兑徘；bfprt通過(guò)修改選擇樞軸的策略刚盈，保證每次partition后< pivot部分和> pivot部分的元素?cái)?shù)量差不多，這樣每次就可以折掉很多數(shù)據(jù)挂脑。
