题意

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

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

思路

• 解决此题主要是利用稳定排序的逆序对的对数的统计，即可知道对应的数组的逆序对，而在稳定排序中，归并排序最快，故选择归并排序来进行统计

题解代码

• cpp

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return mergeSort(0,nums.size()-1,nums,tmp);
    }

    int mergeSort(int l,int r,vector<int>& nums,vector<int>& tmp){
        if(l >= r)
            return 0;
        int m = (l+r)/2;
        int res = mergeSort(l,m,nums,tmp) + mergeSort(m+1,r,nums,tmp);
        int i = l;
        int j = m+1;
        for(int k = l;k <= r;k++){
            tmp[k] = nums[k];
        }
        for(int k = l;k <= r;k++){
            if(i == m+1){
                nums[k] = tmp[j++];
            }
            else if(j == r+1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }
            else if(tmp[i] > tmp[j]){
                res += m-i+1;
                nums[k] = tmp[j++];
            }
        }
        return res;
    }
};

• java

class Solution {
    int[] nums;
    int[] tmp;

    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0,nums.length-1);
    }

    int mergeSort(int l,int r){
        if(l >= r){
            return 0;
        }
        int m = (l+r)/2;
        int res = mergeSort(l,m) + mergeSort(m+1,r);
        int i = l;
        int j = m+1;
        for(int k = l;k <= r;k++){
            tmp[k] = nums[k];
        }
        for(int k = l;k <= r;k++){
            if(i == m+1){
                nums[k] = tmp[j++];
            }
            else if(j == r+1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }
            else{
                res += m-i+1;
                nums[k] = tmp[j++];
            }
        }
        return res;
    }
}