算法原理
利用歸并思想進(jìn)行分治也是很重要的一種思路，在解決逆序?qū)Φ膯栴}上有很大的需求空間
于是首先歸并排序是首先的，歸并排序要能寫出來：
class Solution
{
vector<int> tmp;
public:
vector<int> sortArray(vector<int>& nums)
{
tmp.resize(nums.size());
mergesort(nums,0,nums.size()-1);
return nums;
}
void mergesort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return;
}
// 數(shù)組劃分 [left,mid][mid+1,right]
int mid=(left+right)/2;
// 分塊排序
mergesort(nums,left,mid);
mergesort(nums,mid+1,right);
// 合并數(shù)組
int cur1=left,cur2=mid+1,i=0;
while(cur1<=mid && cur2<=right)
{
if(nums[cur1]<=nums[cur2])
{
tmp[i++]=nums[cur1++];
}
else
{
tmp[i++]=nums[cur2++];
}
}
while(cur1<=mid)
{
tmp[i++]=nums[cur1++];
}
while(cur2<=right)
{
tmp[i++]=nums[cur2++];
}
for(int i=left;i<=right;i++)
{
nums[i]=tmp[i-left];
}
}
};
以上為歸并排序基本算法原理，基于這個(gè)原理可以解決逆序?qū)栴}，逆序?qū)栴}通常問法是，給定某一個(gè)數(shù)據(jù)，在整個(gè)數(shù)組中找比這個(gè)數(shù)大或者比這個(gè)數(shù)小的數(shù)，統(tǒng)計(jì)這樣的元素有多少個(gè)，進(jìn)而返回到數(shù)組或者直接輸出
那么在找尋這個(gè)過程中，這類問題的基本思路就是：左邊找，右邊找，左右找
在找尋的過程中需要注意的是升序和逆序問題，后續(xù)的題目中會(huì)有涉及到的地方，在這里不過總結(jié)
實(shí)現(xiàn)思路
大體的實(shí)現(xiàn)思路如上，總結(jié)下來就是劃分為兩個(gè)子區(qū)間，在左邊找，在右邊找，接著左右找，這樣就能找到要求的結(jié)果
典型例題
排序數(shù)組
理解快速排序和歸并排序思維的不同點(diǎn)
依舊是經(jīng)典的排序數(shù)組問題，這次選用歸并排序來解決，要了解歸并排序和快速排序其實(shí)都是利用了分治的思想，把一個(gè)很復(fù)雜的問題分解為一個(gè)一個(gè)的小問題，二者在思維上有一些小小的區(qū)別，快速排序的思想是，對(duì)于某個(gè)區(qū)間來說，把這個(gè)區(qū)間進(jìn)行分塊，每一個(gè)分塊都進(jìn)行排序，每一個(gè)都進(jìn)行排序，這樣就完成了目的，這樣的思維更像是一種前序遍歷，完成了這次的任務(wù)后再向后進(jìn)行延伸，而歸并排序的思路和快速排序不同，歸并排序的思路主要是把數(shù)組拆分成一個(gè)一個(gè)的小區(qū)間，不停的拆分，直到不能拆分后再進(jìn)行組裝，它的排序過程整體上而言是滯后的，更像是一種后序遍歷的思想，先一直向深處找，直到找不下去了再進(jìn)行排序，再一層一層向上走
class Solution
{
vector<int> tmp;
public:
vector<int> sortArray(vector<int>& nums)
{
tmp.resize(nums.size());
mergesort(nums,0,nums.size()-1);
return nums;
}
void mergesort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return;
}
// 數(shù)組劃分 [left,mid][mid+1,right]
int mid=(left+right)/2;
// 分塊排序
mergesort(nums,left,mid);
mergesort(nums,mid+1,right);
// 合并數(shù)組
int cur1=left,cur2=mid+1,i=0;
while(cur1<=mid && cur2<=right)
{
if(nums[cur1]<=nums[cur2])
{
tmp[i++]=nums[cur1++];
}
else
{
tmp[i++]=nums[cur2++];
}
}
while(cur1<=mid)
{
tmp[i++]=nums[cur1++];
}
while(cur2<=right)
{
tmp[i++]=nums[cur2++];
}
for(int i=left;i<=right;i++)
{
nums[i]=tmp[i-left];
}
}
};
數(shù)組中的逆序?qū)?/h3>
利用歸并排序求逆序?qū)κ墙鉀Q這類問題的常見方法，對(duì)于這個(gè)題來說，就可以采用分治的方法來解決問題
具體來說，可以把整個(gè)問題拆分為幾個(gè)小步驟，把當(dāng)前所在區(qū)間分成兩個(gè)區(qū)間，在左邊的區(qū)間內(nèi)找符合逆序?qū)Φ膶?duì)數(shù)，再在右邊的區(qū)間內(nèi)找符合逆序?qū)Φ膶?duì)數(shù)，同時(shí)把左右兩區(qū)間都進(jìn)行排序，這樣就可以在左右區(qū)間內(nèi)都尋找符合要求的逆序?qū)?shù)，這就是一個(gè)輪回思路，把整個(gè)數(shù)組拆分為一個(gè)一個(gè)小區(qū)間即可解決問題，這就是分治的思想
那么思路就確認(rèn)了：
- 從左邊數(shù)組中找符合要求的逆序?qū)?/li>
- 從右邊數(shù)組中找符合要求的逆序?qū)?/li>
- 從左右兩邊數(shù)組中找符合要求的逆序?qū)?/li>
從排列組合的分類原理來看，這樣就能找到所有的逆序?qū)?/p>
從優(yōu)化角度來講，第三步是可以進(jìn)行優(yōu)化的，這就引入了要排序的原因：
如何從左右兩數(shù)組中找逆序?qū)?shù)？
其實(shí)利用雙指針的思想就可以解決，定義cur1和cur2分別指向左右兩個(gè)數(shù)組，假設(shè)這里是提前排序好的，升序的數(shù)組，那么當(dāng)cur1所指向的元素大于cur2所指的元素，那么cur2所指向的元素之前的元素全部滿足條件，因此一次可以找出很多相同的元素，這也是這個(gè)算法的原理
因此這里就引出了為什么要進(jìn)行排序，左右子區(qū)間排序后就可以通過上面的算法快速找到有多少滿足要求的逆序?qū)?/p>
處理剩余元素
-
如果是左邊出現(xiàn)剩余，說明左邊剩下的所有元素都是?右邊元素?的，但是它們都是已經(jīng)被計(jì)算過的，因此不會(huì)產(chǎn)?逆序?qū)Γ瑑H需歸并排序即可。
-
如果是右邊出現(xiàn)剩余，說明右邊剩下的元素都是?左邊?的，不符合逆序?qū)Φ亩x，因此也不需要處理，僅需歸并排序即可。
class Solution
{
vector<int> tmp;
public:
int reversePairs(vector<int>& nums)
{
tmp.resize(50001);
return mergesort(nums,0,nums.size()-1);
}
int mergesort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return 0;
}
int ret=0,mid=(left+right)/2;
ret+=mergesort(nums,left,mid);
ret+=mergesort(nums,mid+1,right);
int cur1=left,cur2=mid+1,i=0;
while(cur1<=mid && cur2<=right)
{
if(nums[cur1]<=nums[cur2])
{
tmp[i++]=nums[cur1++];
}
else
{
ret+=mid-cur1+1;
tmp[i++]=nums[cur2++];
}
}
while(cur1<=mid)
{
tmp[i++]=nums[cur1++];
}
while(cur2<=right)
{
tmp[i++]=nums[cur2++];
}
for(int i=left;i<=right;i++)
{
nums[i]=tmp[i-left];
}
return ret;
}
};
總體來說還是一道有思維量的hard題目，但如果掌握了分治的思想，再去下手就會(huì)容易許多
而這樣的算法的時(shí)間復(fù)雜度也是很優(yōu)秀的，時(shí)間復(fù)雜度是O(N)
計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)
有了上面的題目的思維鋪墊，解法還是比較好想的，原理就是利用歸并排序進(jìn)行分治的思想
但這個(gè)題和上面的問題也有區(qū)別，由于返回的是數(shù)組，因此需要記錄nums中每一個(gè)數(shù)組中元素在返回?cái)?shù)組中元素的下標(biāo)，需要一一對(duì)應(yīng)起來，這是比較關(guān)鍵的一步，也就是說，每次找到符合條件的數(shù)后，這個(gè)數(shù)應(yīng)該被放到返回?cái)?shù)組中的哪個(gè)位置？這就需要用一個(gè)輔助數(shù)組來記錄原數(shù)組中每一個(gè)元素的下標(biāo)所在的位置，這樣就能找到了文章來源：http://www.zghlxwxcb.cn/news/detail-691574.html
class Solution
{
vector<int> ret;
vector<int> index;
int tmpnums[500010];
int tmpindex[500010];
public:
vector<int> countSmaller(vector<int>& nums)
{
int n=nums.size();
ret.resize(n);
index.resize(n);
for(int i=0;i<n;i++)
{
index[i]=i;
}
mergesort(nums,0,n-1);
return ret;
}
void mergesort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return;
}
int mid=(left+right)/2;
mergesort(nums,left,mid);
mergesort(nums,mid+1,right);
int cur1=left,cur2=mid+1,i=0;
while(cur1<=mid && cur2<=right)
{
if(nums[cur1]<=nums[cur2])
{
tmpnums[i]=nums[cur2];
tmpindex[i++]=index[cur2++];
}
else
{
ret[index[cur1]]+=right-cur2+1;
tmpnums[i]=nums[cur1];
tmpindex[i++]=index[cur1++];
}
}
while(cur1<=mid)
{
tmpnums[i]=nums[cur1];
tmpindex[i++]=index[cur1++];
}
while(cur2<=right)
{
tmpnums[i]=nums[cur2];
tmpindex[i++]=index[cur2++];
}
for(int j=left;j<=right;j++)
{
nums[j]=tmpnums[j-left];
index[j]=tmpindex[j-left];
}
}
};
總結(jié)
歸并遞歸解決分治問題主要依托于歸并排序，在掌握歸并的前提下找到歸并過程中要找的關(guān)鍵信息文章來源地址http://www.zghlxwxcb.cn/news/detail-691574.html
到了這里，關(guān)于算法：分治思想處理歸并遞歸問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
