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

【超详细注释】基本上思路是采用归并排序的方式，思想应该是和剑指书上是一致的
首先将数组二分，直到每一部分只有一个数为止，然后开始合并。

这一部分主要是创建一个临时数组，用来存储归并期间的各个数据

 public int InversePairs(int [] nums) {
    //如果数组的长度为0或者1，肯定不存在逆序对，直接返回0
    if (nums.length < 2) {
        return 0;
    }
    //记录数组的左右边界
    int left = 0;
    int right = nums.length-1;
    //用来存储临时数组
    int[] temp = new int[nums.length];
    //因为int可能会有溢出所以使用long来存储结果，最后取模强转
    long ans = help(nums, left, right, temp) % 1000000007;
    return (int)ans;
}

//统计各个环节的逆序对数量，包括左边数组的逆序对，右边数组的逆序对，合并数组时统计到的逆序对数
private long help(int[] nums, int left, int right, int[] temp) {
    //当左指针 = 右指针直接返回0
    if (left == right) {
        return 0;
    }
    //取中点二分
    int mid = (left + right) >> 1;
    //左边存在的逆序对个数，继续下一层
    long leftSum = help(nums, left, mid, temp);
    //右边存在的逆序对个数，继续下一层
    long rightSum = help(nums, mid + 1, right, temp);
    //将两部分和一部分时产生的逆序对个数
    long heBing = merge(left, mid, right, nums, temp);
    return leftSum + rightSum + heBing;
}

//统计合并数组时的逆序对数，这是核心，因为拆分到只有一个数的时候，就靠合并来得到逆序对数
private int merge(int l, int mid, int r, int[] nums, int[] temp) {
    //将对应的数据拷贝到temp
    for (int i = l; i <= r; i++) {
        temp[i] = nums[i];
    }
    //左侧数组的起点
    int i = l;
    //右侧数组的起点
    int j = mid + 1;
    //逆序对数
    int count = 0;
    for (int k = l; k <= r; k++) {
        //i>=mid +1 表示左边数组已经统计结束，只需要处理右边数组
        if (i >= mid+1) {
            nums[k] = temp[j];
            j++;
        }
        // 表示右边统计结束，只需要继续统计左边
        else if (j >= r + 1) {
            nums[k] = temp[i];
            i++;
        }
        //左边比右边小，说明没有逆序对
        else if (temp[i] < temp[j]) {
            nums[k] = temp[i];
            i++;
        }
        //左边大，说明左边后面的都比右边数组当前数字大，统计逆序对
        else {
            nums[k] = temp[j];
            j++;
            count = count + mid - i + 1;
        }
    }
    return  count;
}

这个做法的缺点就是修改了原数组，程序结束，原数组已经被排序了！！！