题目分析

首先想到的暴力一定不是面试官想要的，暴力的复杂度为n平方
那么比暴力更快一点的复杂度为nlogn，怎么才会有logn出现呢
一半一半就会有logn出现
怎么样把一半一半用到这道题上呢
将数组[1,2,3,4,5,6,0]对半切，变成arr1=[1,2,3,4]和arr2=[5,6,0]
将arr1里的1和arr2的5做比较，发现1<5，要是arr2里的0是7或者8就好了，这样1就比arr2里的所有数字都小了呢，就不存在逆序对了
那么假设arr2排过序了是[0,5,6],刚好arr1目前也是排过序的
1、arr1里的1是大于arr2里的0的，那么arr1里1且其之后的所有数字都比0大，则对于0来说，有4个数字比它大，所以结果变量+4,0被arr1里的所有数字都比较过了（也不是一个个遍历比较，而是用了有序的性质），0就可以被丢弃了（实际上是放到归并排序的临时数组里了）
2、此时1是小于5的，那么可以断定1比arr2里的所有数字都小，也可以把1和之前的0一样处理掉
3、现在arr1=[2,3,4] arr2=[5,6],2小于5，所以2比arr2里的都要小，丢弃，一直循环下去，4也被丢掉，逆序对完成

所以解法就是归并排序，只加了一行res+=mid-i+1;
递归里面运行完两个mergeSort后，start~mid 和 mid+1~end都是有序的，且两个内部的逆序对都已经算过了，只需要算当前状态的逆序对就行了，不会重复的

代码

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++];
        }
    }
}