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

【题目】

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

 

示例 1:

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

 

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof

【思路】

引入归并排序的思想，每一轮归并排序，实际上就是在比较两个数的逆序数，递归进行归并，同时记录每次递归的逆序数，累加就是逆序数的总和。

【代码】

class Solution {
    int[] nums,temp;
    public int reversePairs(int[] nums) {
        this.nums= nums;
        temp = new int[nums.length];
        return mergeSort(0,nums.length-1);
    }
    private int mergeSort(int l,int r){
        if(r<=l) return 0;
        int m = (l+r)/2;
        int res = mergeSort(l,m) + mergeSort(m+1,r);
        int i = l,j = m+1;
        // 将原始数组备份
        for(int k=l;k<=r;k++){
            temp[k]= nums[k];
        }
        for(int k =l;k<=r;k++){
            // 如果i（左边分组已经指向右边起始点）=m+1，则右边的按顺序存入即可
            if(i==m+1){
                nums[k] = temp[j++];
            // 如果j（右边分组已经指向右边终点）=r+1或当前左边指向的数小于右边，则左边按顺序存入即可
            }else if(j==r+1||temp[i]<=temp[j]){
                nums[k] = temp[i++];
            //否则，发生逆序情况，逆序个数为左边数的个数（因为右边小于左边的一个数，代表小于左边那个数右边的所有数） 数量为m-i+1
            }else{
                nums[k] = temp[j++];
                res +=m-i+1;
            }
        }
        return res;
    }
}