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

import java.util.*;


public class Solution {
    private int count = 0;
    private final int MOD = 1000000007;

    public int InversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        mergeSort(nums, 0, nums.length - 1);
        return count;
    }

    private void mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;

        while (i <= mid && j <= end) {
            if (nums[i] > nums[j]) {
                count = (count + (mid - i + 1)) % MOD;
                temp[k++] = nums[j++];
            } else {
                temp[k++] = nums[i++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        while (j <= end) {
            temp[k++] = nums[j++];
        }

        System.arraycopy(temp, 0, nums, start, temp.length);
    }
}

使用归并排序计算逆序对数量，其实就是先拆分，在合并，在合并中，如果对于nums[i]-nums[mid]与nums[j]-nums[end],如果nums[i]>nums[j],则左子数组都是与nums[j]形成了逆序对，然后把nums[j]放入新数组中，继续比较nums[i]与nums[j+1]; 如果nums[i]<nums[j],则把nums[i]放入新数组中，继续比较nums[i+1]与nums[j]，两个数组比完，也就代表这部分的逆序数求出来的，且排好序了，直到只剩一个数组，就结束了。

一开始没理解的地方：

拆分为什么不见新数组：这是因为是隐式拆分，并未形成新的数组；

拆分时为什么要有mid，直接是start到end不是更好：这是因为mid每次重复计算，保证拆分范围是变动的。

新学习的方法的功能：

System.arraycopy 的方法签名如下：

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

参数说明：

• src：源数组，你想要从这个数组中拷贝元素。
• srcPos：源数组中的起始位置，从这个位置开始拷贝。
• dest：目标数组，你想要拷贝元素到这个数组。
• destPos：目标数组中的起始位置，从这个位置开始粘贴拷贝的元素。
• length：要拷贝的元素数量