剑指 Offer 51. 数组中的逆序对 (opens new window)

1.归并排序

• 分析

题意简洁明了，显然时间O(n)算法不可能，O(n平方)超时，往O(n logn)方向考虑。而出现logn常见的算法显然就是二分，或者归并排序。

解法本质上是对原数组排序，以降序版本的归并为例，每次统计左块元素能构成逆序对的数量，左块的指针 i 指向的元素如果大于右块指针 j 的元素，那么i元素能够形成的逆序对数量为right-j。否则移动右半块指针。

此处开辟一个list容器保存合并后的有序数组，最后写回到原数组中。合并时每次都将更大的元素依次加入list。

• 思考

此处排序后交换顺序是否会影响数组元素的逆序对？

对于要合并的两个块【a，b】和【c，d】，最终合并后得到的有序块【c，d，a，b】。交换a的位置只会影响到【c，d，a，b】与【a，b】这两个块的逆序对数量统计，而前者在合并的过程中已经进行了统计，没有影响；而后者既然已经是有序的，说明也已经统计过了。

class Solution {
    int res=0;
    List<Integer> list;
    public int reversePairs(int[] nums){
        if(nums.length==0) return 0;
        list=new ArrayList<>();
        mergesort(nums,0,nums.length-1);
        return res;
    }
    public 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);
        //从大到小排序
        int left=start,right=mid+1;
        while(left<=mid&&right<=end){
            if(nums[left]>nums[right]){
                res+=end-right+1;
                list.add(nums[left]);
                if(left==mid){
                    for(int i=right;i<=end;i++) list.add(nums[i]);
                }
                left++;
            }
            else{
                list.add(nums[right]);
                if(right==end){
                    for(int i=left;i<=mid;i++) list.add(nums[i]);
                }
                right++;
            }
        }
        for(int i=start;i<=end;i++) nums[i]=list.get(i-start);
        list.clear();
    }
}