算法原理
分治的原理就是分而治之,從原理上講,就是把一個(gè)復(fù)雜的問(wèn)題劃分成子問(wèn)題,再將子問(wèn)題繼續(xù)劃分,直到可以解決
實(shí)現(xiàn)思路
基于分治的原理進(jìn)行快速排序,區(qū)別于傳統(tǒng)的快速排序,這里對(duì)快速排序進(jìn)行改良,成為更優(yōu)先的三路劃分算法,可以處理一些極端場(chǎng)景,使快速排序的適用性更加廣泛,同時(shí)引出快速選擇算法,用來(lái)搭配堆排序解決topk
問(wèn)題
典型例題
顏色分類(lèi)
本題和前面在雙指針?biāo)惴ㄖ凶龅?code>移動(dòng)0的解法類(lèi)似,這里其實(shí)算法原理和快速排序優(yōu)化的三路劃分很相似,將數(shù)組中的區(qū)域劃分為三個(gè)部分,分別為0,1,2
,因此解決問(wèn)題的時(shí)候要先想清楚如何解決,把數(shù)據(jù)量弄清楚
對(duì)于此題來(lái)說(shuō),算法思路就是如果遇到2
,就把數(shù)據(jù)扔到最后,如果遇到0
,就放到最前,那么1
就會(huì)被天然的隔離到最中間的部分,這是可行的
快速排序優(yōu)化
根據(jù)上面的原理,可以改進(jìn)快速排序,快速排序的弊端在于,當(dāng)他要進(jìn)行處理很多相同數(shù)據(jù)的時(shí)候,就遇到十分低效的情況,基于這個(gè)原因,可以在實(shí)現(xiàn)它的過(guò)程中利用到一些上面的想法,這樣的算法思路其實(shí)也叫做三路劃分
因此可以使用這個(gè)方法來(lái)解題,否則會(huì)超時(shí)
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
srand(time(0));
quicksort(nums,0,nums.size()-1);
return nums;
}
void quicksort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return;
}
int key=numsrandom(nums,left,right);
int i=left,begin=left-1,end=right+1;
while(i<end)
{
if(nums[i]<key)
{
swap(nums[++begin],nums[i++]);
}
else if(nums[i]==key)
{
i++;
}
else
{
swap(nums[--end],nums[i]);
}
}
quicksort(nums,left,begin);
quicksort(nums,end,right);
}
int numsrandom(vector<int>& nums,int left,int right)
{
int keyi=rand()%(right-left+1)+left;
return nums[keyi];
}
};
基于快速排序的三路劃分原理,可以引申出新的思想:快速選擇問(wèn)題
數(shù)組中最大的K個(gè)數(shù)
看到這個(gè)題第一思想是使用堆排序,因?yàn)槎雅判蛱幚?code>TopK問(wèn)題是十分有效的,但是后面的限制條件,時(shí)間復(fù)雜度必須是O(N)
的算法,因此這里并不能使用TopK
算法
由于前面有快速排序的基礎(chǔ),因此這里可以引申出一個(gè)快速選擇解法
首先看思路:
在快速排序的三路劃分算法中,當(dāng)劃分結(jié)束后,整個(gè)數(shù)組會(huì)被天然的劃分為下面三個(gè)部分:
假設(shè),我們這里讓藍(lán)色區(qū)域的記作C,紅色區(qū)域記作B,棕色區(qū)域記作A
那如果我們要求的這個(gè)第k
個(gè)數(shù)據(jù)落在藍(lán)色區(qū)域
,那么我們只需要在C
這個(gè)單位長(zhǎng)度內(nèi)尋找一次即可,如果落在紅色區(qū)域
,那么要找的這個(gè)數(shù)據(jù)就是key
,如果落在棕色區(qū)域
,則只需要在A
這個(gè)單位長(zhǎng)度尋找一次即可
由此,就引申出了快速選擇算法:基于快速排序從而引申出的快速選擇
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
srand(time(NULL));
return quicksort(nums,0,nums.size()-1,k);
}
int quicksort(vector<int>& nums,int l,int r,int k)
{
if(l==r)
{
return nums[l];
}
// 1. 選取中間元素
int key=getrandom(nums,l,r);
int left=l-1,right=r+1,i=l;
// 2. 三路劃分
while(i<right)
{
if(nums[i]<key)
{
swap(nums[++left],nums[i++]);
}
else if(nums[i]==key)
{
i++;
}
else
{
swap(nums[--right],nums[i]);
}
}
// 3. 判斷
int c=r-right+1;
int b=(right-1)-(left+1)+1;
if(c>=k)
{
return quicksort(nums,right,r,k);
}
else if(b+c>=k)
{
return key;
}
else
{
return quicksort(nums,l,left,k-b-c);
}
}
int getrandom(vector<int>& nums,int l,int r)
{
return nums[rand()%(r-l+1)+l];
}
};
時(shí)間復(fù)雜度分析較為復(fù)雜,但是是嚴(yán)格符合題目要求的,由此其實(shí)也看出了分治的思想核心,把一個(gè)大問(wèn)題轉(zhuǎn)換成小問(wèn)題,直到最后轉(zhuǎn)換成一個(gè)我們一下就能解決的問(wèn)題,不斷的縮小我們需要尋找的區(qū)間,這樣最終就能找到我們需要的答案
最小的K個(gè)數(shù)
class Solution
{
public:
vector<int> getLeastNumbers(vector<int>& nums, int k)
{
srand(time(NULL));
quicksort(nums,0,nums.size()-1,k);
return {nums.begin(),nums.begin()+k};
}
void quicksort(vector<int>& nums,int l,int r,int k)
{
if(l==r)
{
return;
}
// 1. 選基準(zhǔn)元素
int key=getrandom(nums,l,r);
int left=l-1,right=r+1,i=l;
// 2. 三路劃分
while(i<right)
{
if(nums[i]<key)
{
swap(nums[++left],nums[i++]);
}
else if(nums[i]==key)
{
i++;
}
else
{
swap(nums[--right],nums[i]);
}
}
// 3. 快速選擇
int a=left-l+1,b=(right-1)-(left+1)+1;
if(a>k)
{
quicksort(nums,l,left,k);
}
else if(a+b>=k)
{
return;
}
else
{
quicksort(nums,right,r,k-a-b);
}
}
int getrandom(vector<int>& nums,int l,int r)
{
return nums[rand()%(r-l+1)+l];
}
};
對(duì)于這個(gè)題來(lái)說(shuō),解法多種多樣,可以采用很多方法,topk
,直接排序,快速選擇,這里依舊選擇快速選擇來(lái)寫(xiě)
原理和前面類(lèi)似,由于返回的是前k
個(gè)數(shù)不一定要有序,因此三路劃分后可以直接進(jìn)行條件判斷,滿足需求就可以跳出循環(huán)文章來(lái)源:http://www.zghlxwxcb.cn/news/detail-690038.html
總結(jié)
分治思想用以快速排序,可以引申出快速選擇
這個(gè)算法,而這個(gè)算法在實(shí)際應(yīng)用中有很大的作用,對(duì)于解決前k
個(gè)數(shù)或第k
個(gè)數(shù)都有很大的算法意義,下篇會(huì)總結(jié)分治思想用以解決歸并問(wèn)題文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-690038.html
到了這里,關(guān)于算法:分治思想處理快排遞歸以及快速選擇/最小K個(gè)數(shù)問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!