归并排序的过程就是消除逆序对的过程

合并的代码解析

 while(i<=mid && j<=end){
    if(nums[i]<nums[j]){
        temp[k++]=nums[i++];
    }else{
        res+=mid-i+1;
        temp[k++]=nums[j++];
    }
}

具体代码实现:

class Solution {
    private int res=0;
    public int inversePairs(int[] nums) {
        if(nums==null || nums.length<=1) return 0;
        int start=0,end=nums.length-1;
        int[] temp=new int[end+1];
        mergeSort(nums,temp,start,end);
        return res;
    }

    void mergeSort(int[] nums,int[] temp,int start,int end){
        if(start>=end) return;
        int mid=start+(end-start)/2;
        mergeSort(nums,temp,start,mid);
        mergeSort(nums,temp,mid+1,end);
        int i=start,j=mid+1,k=0;
        while(i<=mid && j<=end){
            if(nums[i]<nums[j]){
                temp[k++]=nums[i++];
            }else{
                res+=mid-i+1;
                temp[k++]=nums[j++];
            }
        }
        while(i<=mid) temp[k++]=nums[i++];
        while(j<=end) temp[k++]=nums[j++];
        k=0;
        while(start<=end){
            nums[start++]=temp[k++];
        }
    }
}

回顾一下归并排序的代码
acwing 787 归并排序 / 洛谷 P1177

#include<iostream>

using namespace std;

const int MAXN = 1E5+10;
int arr[MAXN];
int cache[MAXN];

int n;

void mergeSort(int left,int right){
    if(left >= right){
        return;
    }
    int mid = left + right >> 1;
    mergeSort(left,mid);
    mergeSort(mid + 1,right);
    int i = left;
    int j = mid + 1;
    int k = left;
    for(; i <= mid && j <= right;){
        if(arr[i] <= arr[j]){
            cache[k++] = arr[i++];
        }else{
            cache[k++] = arr[j++];
        }
    }
    while(i <= mid){
        cache[k++] = arr[i++];
    }
    while(j <= right){
        cache[k++] = arr[j++];
    }
    for(k = left;k <=right;k++){
        arr[k] = cache[k];
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    mergeSort(1,n);
    for(int i = 1;i <= n; i++){
        cout << arr[i] << ' ';
    }
    cout << endl;
    return 0;
}

然后由上面的图可知，只有右边的区间的数，向下赋值时，才产生逆序对
也就是左边区间中还未下落的数的个数

即 mid - i + 1

将上述代码修改后得逆序对代码
对应题目 ，信息学奥赛一本通 1328：【例7.7】光荣的梦想

#include<iostream>

using namespace std;

const int MAXN = 1E5+10;
int arr[MAXN];
int cache[MAXN];
int ans;

int n;

void mergeSort(int left,int right){
    if(left >= right){
        return;
    }
    int mid = left + right >> 1;
    mergeSort(left,mid);
    mergeSort(mid + 1,right);
    int i = left;
    int j = mid + 1;
    int k = left;
    for(; i <= mid && j <= right;){
        if(arr[i] <= arr[j]){
            cache[k++] = arr[i++];
        }else{
            ans += mid - i + 1;
            cache[k++] = arr[j++];
        }
    }
    while(i <= mid){
        cache[k++] = arr[i++];
    }
    while(j <= right){
        cache[k++] = arr[j++];
    }
    for(k = left;k <=right;k++){
        arr[k] = cache[k];
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    mergeSort(1,n);

    cout << ans << endl;
    return 0;
}