题解 | 数组中的逆序对

import java.util.*;


// public class Solution {
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param nums int整型一维数组
//      * @return int整型
//      */
//     int count = 0;
//     final int MOD = 1000000007;
//     public int InversePairs (int[] nums) {
//         // write code here
//         // //1.暴力求解法-------------超时
//         // int count = 0;
//         // final int MOD = 1000000007;
//         // for(int i = 0;i < nums.length; i ++){
//         //     for(int j = i + 1; j < nums.length; j ++){
//         //         if(nums[j] < nums[i]){
//         //             count ++;
//         //             count %= MOD;
//         //         }
//         //     }
//         // }

//         // return count;
//         //2.方法2：采用归并排序的过程中后进行计算逆序对

//         //1.1数组长度小于2，不存 在逆序对
//         if (nums.length < 2) {
//             return 0;
//         }
//         //1.2进入归并
//         mergeSort(nums, 0, nums.length - 1);
//         return count;
//     }

//     private void mergeSort(int[] nums, int left, int right) {
//         // TODO
//         //2.1划分
//         //找到分割点
//         if(left >= right){
//             return;//若只有一个数字，则停止划分
//         }
//         int mid = left + (right - left) / 2;//避免整数越界
//         if (left < right) {
//             mergeSort(nums, left, mid); //左
//             mergeSort(nums, mid + 1, right); //右
//             //合并
//             merge(nums, left, mid, right);
//         }
//     }

//     private void merge(int[] nums, int left, int mid, int right) {
//         // TODO
//         //1.创建一个临时数组
//         int[] arr = new int[right - left + 1];
//         //保存原始数组的起点下标值
//         int cur = 0;
//         //左边部分起始下标
//         int l = left;
//         //右边下标起始值
//         int r = mid + 1;

//         while (l <= mid && r <= right) { //开始遍历两部分数组
//             if (nums[l] <=
//                     nums[r]) { //左子数组元素小于右边，没有逆序对---------之所以写=号，
//                 //就是为了保证归并排序的稳定性
//                 arr[cur++] = nums[l++];//临时数组右移，左子数组右移
//             } else {
//                 //此时，存在逆序对，逆序对个数= mid + 1 - l;即：左子数组当前剩余元素个数
//                 arr[cur ++] = nums[r ++];//临时数组右移，右子数组右移
//                 count += mid + 1 - l;
//                 count %= MOD;//求模，避免超越整数数值界限
//             }
//         }
//         //若左边还有元素，全部放入临时数组
//         while(l <= mid){
//             arr[cur ++] = nums[l ++];
//         }
//          //若右边还有元素，全部放入临时数组
//         while(l <= mid){
//             arr[cur ++] = nums[r ++];
//         }

//         //最后，将临时数组中的元素放入到原数组的指定下标位置
//         int s = left;
//         for(int num: arr){
//             nums[s ++] = num;
//         }
//     }
// }
public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        // 长度小于2则无逆序对
        if (array.length < 2)
            return 0;
        // 进入归并
        mergeSort(array, 0, array.length - 1);
        return count;
    }

    public void mergeSort(int[] array, int left, int right) {
        // 找分割点
        int mid = left + (right - left) / 2;
        if (left < right) {
            // 左子数组
            mergeSort(array, left, mid);
            // 右子数组
            mergeSort(array, mid + 1, right);
            // 并
            merge(array, left, mid, right);
        }
    }

    public void merge(int[] array, int left, int mid, int right) {
        // 创建临时数组，长度为此时两个子数组加起来的长度
        int[] arr =  new int[right - left + 1];
        // 临时数组的下标起点
        int c = 0;
        // 保存在原数组的起点下标值
        int s = left;
        // 左子数组的起始指针
        int l = left;
        // 右子数组的起始指针
        int r = mid + 1;
        while (l <= mid && r <= right ) {
            // 当左子数组的当前元素小的时候，跳过，无逆序对
            if (array[l] <= array[r]) {
                // 放入临时数组
                arr[c] = array[l];
                // 临时数组下标+1
                c++;
                // 左子数组指针右移
                l++;
            } else { // 否则，此时存在逆序对
                // 放入临时数组
                arr[c] = array[r];
                // 逆序对的个数为    左子数组的终点- 当前左子数组的当前指针
                count += mid + 1 - l;
                count %= 1000000007;
                // 临时数组+1
                c++;
                // 右子数组的指针右移
                r++;
            }
        }

        // 左子数组还有元素时，全部放入临时数组
        while (l <= mid)
            arr[c++] = array[l++];
        // 右子数组还有元素时，全部放入临时数组
        while (r <= right)
            arr[c++] = array[r++];
        // 将临时数组中的元素放入到原数组的指定位置
        for (int num : arr) {
            array[s++] = num;
        }
    }
}