JZ35 数组中的逆序对

暴力超时

public class Solution {
    public int InversePairs(int [] array) {
        int res = 0;
        for(int i=array.length-1; i>=0;i--){
            for(int j=i-1;j>=0;j--){
                if(array[i]<array[j]) res++;
            }
            res = res%1000000007;
        }
        return res;

    }
}

归并
在归并排序的合并过程中
157,269
当出现 逆序 5,2时
从5开始统计 5后面的 middle的前面 即5,7 全部是比2大的逆序数
在整个数组有序的过程中， 就可以统计逆序数对

import java.util.*;

public class Solution {
    int[] nums, temp;
    public int InversePairs(int [] array) {
        this.nums = array;
        temp = new int[nums.length];
        return mergersort(0,array.length-1);
    }

    public int mergersort(int l, int r){
        if(l>=r) return 0;
        // 划分
        int m = (l+r+1)/2;
        int res = mergersort(l, m-1) + mergersort(m, r);


        for(int i=l;i<=r;i++){
            temp[i] = nums[i];
        }
        int i = l;
        int j = m;
        // 合并
        // 注意必须要 i == m  j == r+1 在前面 
        //否则的话 当判断到temp[i] <= temp[j] ij会超出数组范围
        for(int k=l;k<=r;k++){
            if(i == m) nums[k] = temp[j++];
            else if(j == r+1) nums[k] = temp[i++];
            else if(temp[i] <= temp[j])  nums[k] = temp[i++];
            else{
                res = (res + m - i) % 1000000007;
                nums[k] = temp[j++];
            }
        }
        return res;
    }
}