先来谈谈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
新闻热点
疑难解答
