先來談談mergeSort, 它是排序算法的一種，核心思想是：對一個數組nums[0,…,n]，首先把它分成兩部分nums[0,…,mid]和nums[mid+1,…,n],首先兩個子數組是排好序的，只要對兩個子數組進行整合，然后就排好序了，但是我們可以在對數組整合的時候，作好多事情，。。。 根據主定理，T(0,n)=T(0,(n-1)/2)+T((n-1)/2,n)+C, 其中C是合并時的時間復雜度。只有當C遠小于
下面是mergeSort的實現：
class Solution {public: void combineMerge(vector<int>& nums,int s,int m,int e) { vector<int> cache(e-s+1,0); int i=s,j=m+1,r=0; while(i<=m||j<=e) { if(j>e||(i<=m&&nums[i]<nums[j])) cache[r++]=nums[i++]; else cache[r++]=nums[j++]; } copy(cache.begin(),cache.end(),nums.begin()+s); } void whileMergeSort(vector<int>& nums, int s, int e) { if(s>=e) return ; int mid=s+(e-s)/2; whileMergeSort(nums,s,mid);//前半數組排好序 whileMergeSort(nums,mid+1,e);//后半數組排好序 combineMerge(nums,s,mid,e); }};這里的combineMerge函數的復雜度決定了這里分治算法的復雜度，因為其復雜度為
可以做的事情一：Reverse Pairs
class Solution {public: int reversePairs(vector<int>& nums) { return whileMergeSort(nums,0,nums.size()-1); } int whileMergeSort(vector<int>& nums, int s, int e) { if(s>=e) return 0; int mid=s+(e-s)/2; int cnt=whileMergeSort(nums,s,mid)+whileMergeSort(nums,mid+1,e); /*i是前半數組的指針，j是后半組的指針；必定i<j 題目條件：i<j且nums[i]/2>nums[j] */ for(int i = s, j = mid+1; i<=mid; i++){ while(j<=e && nums[i]/2.0 > nums[j]) j++; //不滿足nums[i]/2>nums[j]時退出，滿足的有[mid+1,...,j-1] cnt += j-(mid+1); } combineMerge(nums,s,mid,e); return cnt; } void combineMerge(vector<int>& nums,int s,int m,int e) { vector<int> cache(e-s+1,0); int i=s,j=m+1,r=0; while(i<=m||j<=e) { if(j>e||(i<=m&&nums[i]<nums[j])) cache[r++]=nums[i++]; else cache[r++]=nums[j++]; } copy(cache.begin(),cache.end(),nums.begin()+s); }};可以做的事情二：Count of Smaller Numbers After Self
class Solution {public: vector<int> countSmaller(vector<int>& nums) { int n=nums.size(); vector<int> smaller(n,0); if(!n) return smaller; vector<int> vec(n,0),copy(n,0); for(int i=0;i<n;i++) vec[i]=i; whileMergeSort(nums,vec,copy,0,n-1,smaller); return smaller; } void whileMergeSort(vector<int>& nums,vector<int>& vec,vector<int>& copy,int s,int e,vector<int>& smaller) { if(s>=e) return; int mid=s+(e-s)/2; whileMergeSort(nums,vec,copy,s,mid,smaller); whileMergeSort(nums,vec,copy,mid+1,e,smaller); /* 這里的題目要求是：對任意一個nums[i]，滿足如下的條件：i<j且nums[i]>nums[j]計數。因此這里的排序，nums不變，只是記錄下標的vec改變。但必有vec[s,..,mid]<vec[mid+1,...,e] */ int i=s,j=mid+1,k=s; while(i<=mid||j<=e) { if(j==e+1||(i<=mid &&nums[vec[i]]<=nums[vec[j]])) { copy[k++]=vec[i];//用于對vec排序 smaller[vec[i]]+=j-mid-1;//下標vec[mid+1,...,j]的nums小于nums[vec[i]] i++; }else copy[k++]=vec[j++]; } for(i=s;i<=e;i++) vec[i]=copy[i]; } };可以解決的事情三：Count of Range Sum
class Solution {public: int countRangeSum(vector<int>& nums, int lower, int upper) { int n=nums.size(); vector<long> sums(n+1,0); for(int i=0;i<n;i++) sums[i+1]=sums[i]+nums[i]; //這里nums[i,...j]的和：sums[j+1]-sums[i] //因此找到在[lower,upper]之間的rangeSum的條件可以看成: //i<=j且lower<=sums[j]-sums[i]<=upper return countMergesort(sums,0,n,lower,upper); } int countMergesort(vector<long>& sums,int s,int e,int low,int up) { if(e-s<1) return 0; int mid=s+(e-s)/2; int count=countMergesort(sums,s,mid,low,up)+countMergesort(sums,mid+1,e,low,up); /* 這里對sums進行排序，前半部分和后半部分的sums都是已排好序的； 這里要對前半部分的任意i,找到起始點k，sums[k]-sums[i]>=low,k之后到e都滿足〉=low; 找到結束點j,使sums[j]-sums[k]<=up，j之前到mid+1的點都滿足<=up. 兩者的重合:[k,...,j-1] */ int j,k,t;j=k=t=mid+1; vector<long> cache(e-s+1,0); for(int i=s,r=0;i<=mid;++i,++r) { while(k<=e&&sums[k]-sums[i]<low) k++; while(j<=e&&sums[j]-sums[i]<=up) j++; while(t<=e&&sums[t]<sums[i]) cache[r++]=sums[t++]; cache[r]=sums[i];//方便對sums排序 count+=j-k; } copy(cache.begin(),cache.begin()+t-s,sums.begin()+s); sort(sums.begin()+s,sums.begin()+e); return count; }};總結：用Divide and Conquer方法可以解決許多類似的問題，一般能用此方法解決的問題，都可以用BST,BIT,segment Tree。。。 參考資料： 1. Mergesort solution 2. Very Short and Clear MergeSort & BST java Solutions 3. Share my solution
新聞熱點
疑難解答
