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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int res = 0;
    //合并过程
    void merge(vector<int>& nums,int l,int r,int mid){
        int left = l;
        int right = mid + 1;
        //申请一个临时数组
        int index = 0;
        vector<int> tmp(r - l + 1);
        //存入临时数组，此时临时数组是有序的
        while(left <= mid && right <= r){
            //如果左边小于右边，则正常插入
            if(nums[left] <= nums[right]){
                tmp[index] = nums[left];
                left += 1;
            }
            else{//如果右边小于左边那么说明存在逆序对，
                tmp[index] = nums[right];
                //如何判断有多少个逆序对呢？因为当前遍历的左边区间下标为index的元素大于右边的，所以，左边index以后的元素都要大于当前下标为right的元素，所以用mid - left + 1.
                res =  (res + mid - left + 1) % 1000000007;
                right += 1;
            }
            index += 1;
        }
        while(left <= mid){
            tmp[index] = nums[left];
            left += 1;
            index += 1;
        }
        while(right <= r){
            tmp[index] = nums[right];
            right += 1;
            index += 1;
        }
        for(int i = 0;i < tmp.size();i++){
            nums[l] = tmp[i];
            l += 1;
        }
        vector<int>(tmp).swap(tmp);
    }
    //归并排序
    void sort(vector<int>& nums,int l,int r){
        if(l >= r)return;
        int mid = l + (r - l) / 2;

        //切割左边的部分
        sort(nums,l,mid);
        //切割右边的部分
        sort(nums,mid + 1,r);

        //当左右边都有序的时候，就合并
        merge(nums,l,r,mid);
    }
    int InversePairs(vector<int>& nums) {
        // write code here
        sort(nums,0,nums.size() - 1);
        for(int val : nums){
            cout << val << " ";
        }
        return res;      
    }
};

该题使用归并排序，通过归并排序的递归分割原数组，直到当前子数组长度为1，此时每个段都是有序的，然后将左右有序数组合并起来，在合并的过程中，如果左边遍历到的元素大于右边遍历到的元素，也就是存在逆序对，此时左边遍历到的位置的后面的所有元素都会大于右边的元素，这可以确定逆序对的数量，也就是mid - left + 1。该题解的时间复杂度是O(nlogn)，空间复杂度是 O(n)。