分治-归并排序-逆序对问题
目录
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 {
public:vector<int> tmp; // 临时数据数组vector<int> count; // 结果数组vector<int> index; // 原始索引数组vector<int> tmpIdx; // 临时索引数组vector<int> countSmaller(vector<int>& nums) {int n = nums.size();tmp.resize(n);count.resize(n, 0);index.resize(n);tmpIdx.resize(n);// 初始化原始索引for(int i = 0; i < n; ++i) index[i] = i;mergesort(nums, 0, n-1);return count;}void mergesort(vector<int>& nums, int low, int high) {if(low >= high) return;int mid = low + (high - low)/2; // 防溢出mergesort(nums, low, mid);mergesort(nums, mid+1, high);merge(nums, low, mid, high);}void merge(vector<int>& nums, int low, int mid, int high) {int left = low, right = mid+1, i = 0;// 合并并统计while(left <= mid && right <= high) {if(nums[left] > nums[right]) {// 右元素更小：存入临时数组并计数tmp[i] = nums[left];tmpIdx[i] = index[left]; // 记录原始索引count[index[left]]+=high-right+1;left++;i++;} else {// 左元素更大或等于：累加已处理的右元素数tmp[i] = nums[right];tmpIdx[i] = index[right]; // 记录原始索引right++;i++;}}// 处理剩余左半部分（补充统计）while(left <= mid) {tmp[i] = nums[left];tmpIdx[i] = index[left];left++;i++;}// 处理剩余右半部分（无需统计）while(right <= high) {tmp[i] = nums[right];tmpIdx[i] = index[right];right++;i++;}// 写回原数组并更新索引for(int id = 0; id < i; ++id) {nums[low + id] = tmp[id];index[low + id] = tmpIdx[id]; // 正确传递原始索引}}
};