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

归并排序

public class Solution {
    int res = 0;
    int [] temp;
    public int InversePairs(int [] array) {
        int n = array.length;
        if(n < 2) return 0;
        temp = new int[n];
        merge_sort(array, 0, n - 1);
        return res;
    }
    public void merge_sort(int[] array, int left, int right){
        if(left >= right) return;
        int mid = (left + right) / 2;
        merge_sort(array,left,mid);
        merge_sort(array,mid + 1,right);
        int i = left, j = mid + 1, index = left;
        while(index <= right){
            if(i > mid || (j <= right && array[i] > array[j])) {
                temp[index++] = array[j++];
                res = (res +  mid - i + 1)% 1000000007;
            }
            else {
                temp[index++] = array[i++];
            }
        }
        for(int s = left; s <= right; s++) {
            array[s] = temp[s];
        }
    }
}