原题（来源Leetcode）

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

解法

思想

暴力：双重循环检查，leetcode中超时

分治思想：使用归并排序的算法，每次给左右两个数组合并的时候，若右边数组中指向的元素小于左边数组指向的元素，则也小于左边数组指向的元素后面的任何一个元素（归并排序合并的时候左右两个数组都是有序的），则此时加上左边数组剩余的元素个数即可。

代码

归并排序大复习，这里提供两种写法：

下面是归并排序较简单的写法，就是每次将数组均分成两个子数组，分到不能再分的时候开始合并相邻的两个子数组。这种写法递归中会创建新数组并拷贝，因此时间成本会略高些。

class Solution {
    int count;//全局变量计数
    public int reversePairs(int[] nums) {
        MergeSort(nums);
        return count;
    }
    public int[] MergeSort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    public int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i == left.length)
                result[index] = right[j++];
            else if (j == right.length)
                result[index] = left[i++];
            else if (left[i] > right[j]){
                count+=left.length-i;//加上左边数组剩余的元素个数
                result[index] = right[j++];
            }
            else result[index] = left[i++];
        }
        return result;
    }
}

下面是一种递归过程中不用创建数组的归并排序写法，只使用两个和原数组相同大小的数组来回交换数据（做对方的缓存），在局部上操作，时间成本会比上面创建数组的方法更低些，但是是一个量级的，在leetcode中能取得更好的成绩：

class Solution {
    public int reversePairs(int[] nums) {
        int[] temp = nums.clone();//创建一个和原数组相同大小的数组
        return MergeSort(nums, temp, 0, nums.length - 1);
    }

    //[start,end]确定一个数组范围，即递归中要排序的范围，返回值为合并过程中的计数
    private int MergeSort(int[] nums, int[] temp, int start, int end) {
        if (start >= end) return 0;
        int mid = (start + end)/2;
        int left = MergeSort(temp, nums, start, mid);
        int right = MergeSort(temp, nums, mid + 1, end);

        int count = merge(nums, temp, start, mid+1, end);
        return left + right + count;
    }

    //[left,right)和[right,end]确定数组的两部分，合并temp数组中的这两部分到nums数组
    private int merge(int[] nums, int[] temp, int left, int right, int end) {
        int index = left;
        int leftSize = right;//因为直接使用left和right作为后面使用的双指针，这里保存right原位置作为left指针能移动到的最远处
        int count = 0;//合并过程中计数

        while (index <= end) {
            if (left==leftSize) nums[index] = temp[right++];
            else if (right==end+1) nums[index] = temp[left++];
            else if (temp[left] > temp[right]) {
                count += (leftSize - left);//加上左边部分剩余的元素个数
                nums[index] = temp[right++];
            } else nums[index] = temp[left++];
            index++;
        }

        return count;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%89%91%e6%8c%87offer51-%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e9%80%86%e5%ba%8f%e5%af%b9/