题解 | #数组中的逆序对#

typedef long long LL; 
#define mod 1000000007;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
     // 对数组进行归并排序
     // 排序的过程中记录逆序对的数量
    LL merge_sort(vector<int>& nums, LL l, LL r){
        if(l >= r) return 0; // 结束标志
        LL res = 0;
        LL mid = l + r >> 1;  // mid位置
        // 先对两边的进行排序
        res =  merge_sort(nums, l, mid) + merge_sort(nums, mid+1, r);

        vector<int> tmp; // 临时数组
        int i = l,j = mid+1;
        while( i<=mid && j <= r){  // 可以等
            if(nums[i] <= nums[j]) {
                tmp.push_back(nums[i]);
                i++;
            }
            else {
                tmp.push_back(nums[j]);
                j++;
                res += mid - i + 1; // mid和i之间的都构成逆序
            }
        }

        while(i <= mid) tmp.push_back(nums[i++]);
        while(j <= r) tmp.push_back(nums[j++]);

        for(int i=l, j=0; i<=r; i++, j++)  nums[i] = tmp[j];

        return res % mod;

    }

    int InversePairs(vector<int>& nums) {
        // write code here
        int n = nums.size();

        LL ans = merge_sort(nums, 0, nums.size()-1);
        
        return ans;
    }
};

解题思路：

使用归并排序记录逆序对，注意每次结果加的数量

注意：排序结束的标志，结果的范围，以及最后要取模

时间复杂度：

nlogn

归并排序的时间复杂度