算法原理
分治的原理就是分而治之，從原理上講，就是把一個(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)！
