剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

输入: [7,5,6,4]
输出: 5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    int[] tmp;
    int count = 0;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        tmp = new int[n];
        merge_sort(nums, 0, n - 1);

        return count;
    }

    public void merge_sort(int[] nums, int l, int r) {
        if (l >= r) return;

        int mid = l + r >> 1;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else {
                count += (mid - i + 1);
                tmp[k++] = nums[j++];
            }
        }

        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
    }
}