题解 | #数组中的逆序对#TOP20

思路:
二分法，假如左边的数比右边的大，2、1 这是一个逆序对，那例如 [4、3]、[2、1] 呢？以2为基准，当遍历到4的时候，有一个逆序对，右侧数组往后移，又是一个逆序对，然后左侧数组回到3位置，和右侧数组去匹配逆序对。假如我们先排好[4,3]，[2,1]有一个逆序对，记录一下。然后将[4,3]变成[3,4]，然后和[1,2]去匹配，3比1大，所以4都不需要遍历，直接3后面的所有数和1匹配都是逆序对。然后再用3和 2 比较，同理
图片摘抄自Dylan

public class Solution {
    public int InversePairs(int [] array) {
        if(array == null || array.length <= 1){
            return 0;
        }
        return mergeSort(array, 0 , array.length - 1) % 1000000007;
        
    }
  
    private int mergeSort(int[] array, int left, int right){
        int mid = left + (right - left) / 2;
        if(left < right){
             int leftCount = mergeSort(array, left, mid);
             int rightCount = mergeSort(array, mid + 1, right);
            int count =  leftCount + rightCount + merge(array,left, mid ,right);
            return count % 1000000007;
        }
        return 0;
    }
    private int merge(int[] array, int left, int mid, int right){
        int[] temp = new int[right - left + 1];
        int tempIndex = 0;
        //原数组的起点位置 就是在array中的位置
        int arrayIndex = left;
        //左子树的下标起点
        int leftIndex = left;
        //右子树的起始位置
        int rightIndex = mid + 1;
        int count = 0;
        while(leftIndex <= mid && rightIndex <= right){
            if(array[leftIndex] <= array[rightIndex]){
                //不是逆序对
                temp[tempIndex++] = array[leftIndex++];
            }else{
                //存在逆序对 左边比右边大
                temp[tempIndex ++] = array[rightIndex++];
                //左子树当前位置后都比这个数大，所以当前位置到mid位置都是逆序对
                //mid  - leftIndex  + 1 
                count += mid +1 -leftIndex;
                count %= 1000000007; 
            }
        }
        while(leftIndex <= mid){
            //左子树还没遍历完
            temp[tempIndex ++] = array[leftIndex ++];
        }
        while(rightIndex <= right){
            temp[tempIndex ++] = array[rightIndex++];
        }
        
        //left - right 这段数组已经排好序了 ,left ,mid 的数一定比mid + 1 ,right 小
        for(int num : temp){
            array[arrayIndex++] = num;
        }
        return count;
    }
}