题目描述

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

输入一个数组，求出这个数组中的逆序对的总数。

样例

样例
输入：[1,2,3,4,5,6,0]

输出：6

算法1

(归并) $O(nlog(n))$

逆序对个数 = 左区间逆序对个数 + 右区间逆序对个数 + 两个区间中构成逆序对个数
因为左右区间内部排好序，逆序对计算出来之后，左右区间有序，不再存在逆序对，右区间 再和 左区间比较，之间不存在交集。

C++ 代码

class Solution {
public:
    //归并 1，找到中点. 2，递归  3归并
    int merge_sort(vector<int> &nums, int l, int r){
        if(l >= r) return 0;

        int mid = l + r >> 1, i = l, j = mid + 1;
        int res = merge_sort(nums, i, mid) + merge_sort(nums, j, r);

        vector<int> tmp(r - l + 1, 0);
        int k = 0;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else{
                tmp[k++] = nums[j++];
                res += mid - i + 1;
            }
        }
        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= r) tmp[k++] = nums[j++];

        i = l, k = 0;
        for(;i <= r; ++i){
            nums[i] = tmp[k++];
        }

        return res;
    }
    int inversePairs(vector<int>& nums) {
        return merge_sort(nums, 0, nums.size() - 1);
    }
};