数组中的逆序对--归并中的计数（分治）

0x01.问题

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

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

来自《剑指offer》

public int reversePairs(int[] nums)

0x02.解决思路

看问题，并不复杂，对于每一个数，只需要找出后面比它小的数的个数，最后累加起来，就是最终的答案，于是可以暴力的写出两层循环的代码，但是，这个时间复杂度达到了O（N^2），对于五位数的数组长度来说，已经无法在短时间内计算出来了，所以必须进行更高效的优化。

再来回想一下我们看到这个问题的第一想法，逆序，大于，这些字眼，都刺激着我们，似乎可以排序，但仔细去想一下排序的思路，排完序的时候，整个数组已经变了， 里面元素的关系也完全变了，而题目中的逆序，很明显是跟元素之间的先后位置有关的，所以，很快就打消了排序的思路。

再仔细想想，好像暂时没有更好的办法了，对于这个问题的话，扫描数组一遍的话肯定是不可能的，也就是说，O(N)的复杂度是不现实的，那么我们就需要想办法将这个复杂度降为介于O（N^2）和O（N）复杂度，最容易想到的，那就是O（N*logN）。对于这种复杂度，要么递归，要么二分。到这里为止，最为符合的应该就是分治了，分而治之。

怎么进行分治了，发现问题还是回到了排序了，我们虽然不能直接进行排序解决这个问题，但我们可以利用归并排序的中间过程去计算数量，在这个中间过程，这个位置关系还是满足的。

我们回顾一下归并排序的具体做法，在合并的步骤中，应该是这样的：

• 从左到右，依次比较一个元素，小者加入合并后的新数组。

在这个归并的过程中，我们是不是可以确定没一个元素和后面一个数组的大小关系，可以计算出比它大的数有多少，并且位置关系是完全满足的。

• 可能你会有一个疑问，那么，在当前这个子数组中呢？位置不是已经变了，嘛，变成排序之后的了。

• 你可能忘了归并是先分解到最小才开始排序的，也就是说，在数组中只有一个元素的时候，合并成这个数组后，这些数目已经计算进去了，并且是递归进去的。

在有了这条最基本的思路，我们可以去完善我们解决这个问题的大体思路了：

• 模拟归并排序的过程，在每次排序的过程中，合成新数组之前，进行计数，计算符合题目要求的数组，最后累加返回。

0x03.解决代码–归并排序（分治）

class Solution {
    private int mergeSort(int[] nums,int[] temp,int left,int right){
        if(left>=right){
            return 0;
        }
        int mid=(left+right)/2;
        //分解的过程
        int count=mergeSort(nums,temp,left,mid)+mergeSort(nums,temp,mid+1,right);
        int i=left;//控制左边下标
        int j=mid+1;//控制右边下标
        int index=left;//控制新数组的下标
        while(i<=mid&&j<=right){
            if(nums[i]<=nums[j]){//左边的小
                temp[index++]=nums[i++];
                count+=j-(mid+1);//归并中符合条件的个数
            }else{//右边的小
                temp[index++]=nums[j++];
            }
        }
        //左边有剩余
        for(int k=i;k<=mid;k++){
            temp[index++]=nums[k];
            count+=j-(mid+1);//每一个数都满足条件
        }
        //右边有剩余
        for(int k=j;k<=right;k++){
            temp[index++]=nums[k];
        }
        //将已完成的temp拷贝到nums
        for (int k = left; k <=right; k++){
            nums[left+k-left] = temp[k];
        }
        return count;
    }
    public int reversePairs(int[] nums) {
        int n=nums.length;
        int[] temp=new int[n];//归并过程中需要的新数组
        return mergeSort(nums,temp,0,n-1);
    }
}

ATFWUS --Writing By 2020–04-24