目錄

1.升序（以右邊的合并組為基準）

2.降序（以左邊的合并組為基準）

?3.逆對序--固定下標

1.升序（以右邊的合并組為基準）

找出左邊有多少個數比我(nums[right])大

• 應該在每一次合并之前，進行逆序對查找
• 每一個該合并的組都是按升序排列，所以當nums[left]<nums[right]時，應該left++，因為都是升序，所以當nums[left]>nums[right]，right++時，left從當前位置不動。

class Solution {
public:vector<int> ret;int vim=0;int reversePairs(vector<int>& record) {ret.resize(record.size());mergesort(record,0,record.size()-1);return vim;}void merge(vector<int>&nums,int low,int high,int mid){int left=low,right=mid+1, i=0;while(left<=mid&&right<=high){if(nums[left]<=nums[right]) ret[i++]=nums[left++];else  {ret[i++]=nums[right++];vim+=(mid+1-left);}}while(left<=mid) ret[i++]=nums[left++];while(right<=high) ret[i++]=nums[right++];for(int i=0;i<high-low+1;i++){nums[i+low]=ret[i];}}void mergesort(vector<int>&nums,int low,int high){if(low>=high) return;int mid=(low+high)/2;mergesort(nums,low,mid);mergesort(nums,mid+1,high);merge(nums,low,high,mid);}
};

2.降序（以左邊的合并組為基準）

?找出多少個數比我小

?合并過程：

?

class Solution {
public:vector<int> ret;int vim=0;int reversePairs(vector<int>& record) {ret.resize(record.size());mergesort(record,0,record.size()-1);return vim;}void merge(vector<int>&nums,int low,int high,int mid){int left=low,right=mid+1, i=0;while(left<=mid&&right<=high){if(nums[left]>nums[right]) {vim+=(high-right+1);ret[i++]=nums[left++];}else  {ret[i++]=nums[right++];}}while(left<=mid) ret[i++]=nums[left++];while(right<=high) ret[i++]=nums[right++];for(int i=0;i<high-low+1;i++){nums[i+low]=ret[i];}}void mergesort(vector<int>&nums,int low,int high){if(low>=high) return;int mid=(low+high)/2;mergesort(nums,low,mid);mergesort(nums,mid+1,high);merge(nums,low,high,mid);}
};

?對比：

降序

升序

void merge(vector<int>&nums,int low,int high,int mid) ? ? { ? ? ? ? int left=low,right=mid+1, i=0; ? ? ? ? while(left<=mid&&right<=high) ? ? ? ? { ? ? ? ? ? ? ?if(nums[left]>nums[right])? ? ? ? ? ? ? ?{ ? ? ? ? ? ? ? ? vim+=(high-right+1); ? ? ? ? ? ? ? ? ret[i++]=nums[left++]; ? ? ? ? ? ? ?} ? ? ? ? ? ? else ? ? ? ? ? ? ? ?ret[i++]=nums[right++]; } ? ? ? ? while(left<=mid) ret[i++]=nums[left++]; ? ? ? ? while(right<=high) ret[i++]=nums[right++]; ? ? ? ? for(int i=0;i<high-low+1;i++) ? ? ? ? { ? ? ? ? ? ? nums[i+low]=ret[i]; ? ? ? ? } ? ? }

?void merge(vector<int>&nums,int low,int high,int mid) ? ? { ? ? ? ? int left=low,right=mid+1, i=0; ? ? ? ? while(left<=mid&&right<=high) ? ? ? ? { ? ? ? ? ? ? ?if(nums[left]<=nums[right]) ????????????????ret[i++]=nums[left++]; ? ? ? ? ? ? else ? ? ? ? ? ? ? { ? ? ? ? ? ? ? ? ret[i++]=nums[right++]; ? ? ? ? ? ? ? ? vim+=(mid+1-left); ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? while(left<=mid) ret[i++]=nums[left++]; ? ? ? ? while(right<=high) ret[i++]=nums[right++]; ? ? ? ? for(int i=0;i<high-low+1;i++) ? ? ? ? { ? ? ? ? ? ? nums[i+low]=ret[i]; ? ? ? ? } ? ? }

?3.逆對序--固定下標

增加一個下標數據，和交換下標數組，當交換數組發生數據交換時，交換下標數組也要發生數據交換

?

class Solution {vector<int> tempnums,index,tempindex,count;
public:vector<int> countSmaller(vector<int>& nums) {int n=nums.size();tempnums.resize(n);//交換數組tempindex.resize(n);//交換下標index.resize(n);//存放原始下表count.resize(n);//存放結果for(int i=0;i<n;i++) index[i]=i;mergesort(nums,0,n-1);return count;}void merge(vector<int>&nums,int low,int high,int mid){int left=low,right=mid+1,i=0;while(left<=mid&&right<=high){if(nums[left]>nums[right]) {tempnums[i]=nums[left];tempindex[i]=index[left];count[index[left]]+=(high-right+1);i++;left++;}else{tempindex[i]=index[right];tempnums[i]=nums[right];i++;right++;}}while(left<=mid){tempnums[i]=nums[left];tempindex[i]=index[left];i++;left++;}while(right<=high){tempindex[i]=index[right];tempnums[i]=nums[right];i++;right++;}for(int j=0;j<i;j++){nums[j+low]=tempnums[j];index[j+low]=tempindex[j];}}void mergesort(vector<int>&nums,int low,int high){if(low>=high) return ;int mid=(low+high)>>1;mergesort(nums,low,mid);mergesort(nums,mid+1,high);merge(nums,low,high,mid);}
};