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

1、什么是逆序对？

1、2、3、4、5、0 【5个】

①1、0

②2、0

③3、0

④4、0

⑤5、0

可以理解是冒泡排序的交换次数，交换5次就是5个逆序对，但是这样的时间复杂度就是O(n^2)了，我们需要O(logn)

2、把1、2、3、4、5、0 二分为 【1、2、3】 【 4、5、0】俩个数组再继续分，直到都是单个数组的时候停止

①将【left，mid】 和【mid+1，right】 俩个氛围的数组合并，由于这是left == right，所以就是单个元素数组合并。

②给左右俩边数组的第一个元素分别赋值指针下标 i = left ， j = mid+1，我们要利用升序的这一与逆序的反策略来比较元素。

把来个数组的第一个元素来对比，如果左边 > 右边，那就说明左边的最小元素都 > 右边的最小元素 （当前数组是一个元素，我们可以假定是升序的），然后我们就直到左边数组的长度可以和右边数组第一个元素组成逆序对，因为左边都大于右边第一个。所以个此次逆序对的个数是mid - i + 1，然后把比较了的右一元素放到原数组中去（让原数组从小到大排列这样和下一个数组合并就不会有重复了），要保证对应的下标，也就是left到right中的第一个。

然后j++，指下一个元素。如此循环。

③分析边界条件，再把最后的结果取模；

import java.util.*;


public class Solution {

    public int mod = 1000000007;

    public int InversePairs (int[] nums) {
        // write code here
        int n = nums.length;
        int[] res = new int[n];
        return mergeSort(0, n - 1, nums, res);
    }

    public int mergeSort(int left, int right, int[] data, int[] temp) {
        // 停止划分
        if (left >= right) {
            return 0;
        }
        // 取中间经典bug，防止过大超出int
        int mid = left + (right - left) / 2;
        // 左右划分合并
        int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data,
                  temp);
        // 防止溢出
        res %= mod;
        
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            temp[k] = data[k];
        }
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                data[k] = temp[j++];
            } else if (j == right + 1 || temp[i] <= temp[j]) {
                data[k] = temp[i++];
            } else {
                //左边比右边大，答案增加
                data[k] = temp[j++];
                // 统计逆序对
                res += mid - i + 1;
            }
        }
        return res % mod;
    }
}