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

import java.util.Arrays;

public class Solution {
    public int InversePairs(int [] array) {
        //方法一：遍历数组
//        int len = array.length;  //获取数组的长度
//        //特殊值处理，当数组长度为0时，此时没有逆序对
//        if(len == 0){
//            return 0;
//        }
//        int count = 0;  //计数器
//        //2层遍历数组，如果前面一个数字大于后面的数字，计数器加1
//        for(int i=0;i<len-1;i++){
//            for(int j=i+1;j<len;j++){
//                if(array[i] > array[j]){
//                    count++;
//                }
//            }
//        }
//        return count%1000000007;

        //方法二：归并排序统计,利用数组的部分有序性
        int len = array.length;  //获取数组的长度
        //特殊值处理，当数组长度为0时，此时没有逆序对
        if(len == 0){
            return 0;
        }
        int count = 0;  //计数器
        count = mergeSortCount(array,0,len-1);
        return count%1000000007;
    }
    
        /**
     * 题目描述：归并排序统计
     * @param arr  原数组
     * @param left 有效数组左边下标索引
     * @param right 有效数组有边下标索引
     * @return
     */
    public static int mergeSortCount(int[] arr,int left,int right){
        int length = right-left+1;  //获取待排序数组的实际长度
        int count = 0;
        if(length == 1){//递归出口，当数组有效长度为1时，数组已有序，没有逆序对
            return 0;
        }
        if(length == 2){//递归出口，当数组有效长度为2时，对数组排序，统计逆序对
            if(arr[left] > arr[right]){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                count = 1;
            }
            return count;
        }
        if(length > 2){
            int mid = (left + right)/2;
            int leftCount = mergeSortCount(arr, left, mid);
            int rightCount = mergeSortCount(arr,mid+1,right);
            count = leftCount+rightCount;
            int j=mid+1;
            //统计逆序对
            for(int i=left;i<=mid;i++){
                for(;j<=right;){
                    if(arr[i] > arr[j]){
//                         count += (mid-i+1);  
                        count = (count+(mid-i+1))%1000000007;//注意，上面的写法可能会存在中间值溢出，所以必须取模
                        j++;
                    }else {
                        break;
                    }
                }
            }
            //排序
            Arrays.sort(arr,left,right+1);
            return count;
        }
        return count;
    }
}