51-数组中的逆序对

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

举例 7 5 4 6

暴力解法

我们先看第一个元素7，存在逆序对是（7,5）（7,4）（7,6），然后再看5，存在逆序对是（5,4）

这个过程可以翻译为两层循环，对每一个元素，依次和其后续每一元素比较大小，符合逆序对则增加1。

这种暴力方法比较简单，时间复杂度是O(n^2)

分治解法

假如我们将数组一分为二，变为 [7 5] [4 6]，看看有什么规律可以得到整个数组的逆序对。

首先先看各个组内的逆序对，（7,5）组成一个逆序对，[4 6]没有逆序对，然后我们将[7 5]排序为

[5 7],这时我们尝试合并两个组，合并时计算逆序对，将两个有序数组合并为一个更大的有序数组，比较明显就是

归并排序的思路，我们使用两个指针分别指向两个待合并数组的末端，p指向7,q指向6，因为7>6,而两个小数组都

是有序的，则因为7产生的逆序对就是7和[4,6]中的所有的元素的组合。同样(5,4)组成逆序对。

所以实际上这是一个归并排序的变形，在具体的merge中获取逆序对的个数。

    private int[] aux;

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        aux = new int[nums.length];
        return reversePairsCore(nums, 0,nums.length - 1);
    }
    public int reversePairsCore(int[] nums,int lo,int hi){
        if (lo >= hi) {
            return 0;
        }
        int mid = (lo + hi) >>> 1;
        int left =  reversePairsCore(nums, lo,mid);
        int right = reversePairsCore(nums, mid + 1, hi);
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            aux[i] = nums[i];
        }
        int i = mid;
        int j = hi;
        for (int k = hi; k  >= lo; k--) {
            if(i < lo){
                nums[k] = aux[j--];
            }else if(j <= mid){
                nums[k] = aux[i--];
            }else if(aux[i] > aux[j]){
                nums[k] = aux[i--];
               //仅此处需要计算逆序对的个数
                count += (j - mid);
            }else {
                nums[k] = aux[j--];
            }
        }
        return count + left + right;
    }