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

public class Solution {
    public final long mod = 1000000007;
    private int ans = 0;
    // 在进行归并的时查看是否存在逆序!
    public int InversePairs(int [] arr) {
        if(arr.length < 2) return 0;
        merageSort(arr,0,arr.length -1);
        return ans;
    }
    
    private void merageSort(int[] arr,int l,int r){
        int mid = l + ((r-l)>>1);
        if(r - l < 1) return ;
        merageSort(arr,l,mid);
        merageSort(arr,mid+1,r);
        merageHelper(arr,l,mid,r); 
    }
    
    private void merageHelper(int[] arr,int l,int mid,int r){
        int[] temp = new int[r-l+1];
        int begin = 0, left = l,right = mid + 1; // temp 数组起始位置,左边数组起始位置,右边数组起始位置!
        
        while(left <= mid && right <= r){
            if(arr[left] < arr[right]){
                temp[begin ++] = arr[left ++];
            }else {
                temp[begin ++] = arr[right ++];
                // 逆序数对的对数组合就是 左边的终点 - 当前指针位置 + 1;
                ans += mid + 1 - left;// 存在逆序!
                ans %= mod;
            }
        }
        
        while(left <= mid){
            temp[begin ++] = arr[left ++];
        }
        while(right <= r){
            temp[begin ++] = arr[right ++];
        }
        
        for(int i = l; i <= r; i++){
            arr[i] = temp[i-l];
        }
    }
    
}