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

public class Solution {

    private int res = 0;
    private int[] temp;

    public int InversePairs(int [] array) {
        if(array.length == 0 || array.length == 1){
            return 0;
        }
        temp = new int[array.length];
        mergeSort(array,0,array.length-1);
        return res;
    }

    public void mergeSort(int[] arr,int left,int right){
        if(left >= right){
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeSort(arr,left,mid);
        mergeSort(arr,mid + 1,right);

        int i = left;
        int j = mid + 1;
        int ids = 0;
        while(i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                temp[ids++] = arr[i++];
            } else {
                res = (res + mid + 1 - i) % 1000000007;
                temp[ids++] = arr[j++];
            }
        }

        while(i <= mid){
            temp[ids++] = arr[i++];
        }
        while(j <= right){
            temp[ids++] = arr[j++];
        }

        // 特别重要，每一次回溯一次，将temp里面临时存放的数组还回到array里面去
        for(int k = 0; k <= right - left; k++) {
            arr[k + left] = temp[k];
        }

    }
}