题解 | 数组中的逆序对

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    
    int coreCode(vector<int>& nums, vector<int>& temp, int left, int right){
        if(left>=right) return 0;//指向同一个位置也是没有逆序数了
        int mid = (left+right)/2;
        int pairs = (coreCode(nums, temp, left, mid)+coreCode(nums, temp, mid+1, right))%1000000007;
        int cur = left;
        int lpos = left, rpos = mid+1;
        while(cur<=right){
            if(lpos<=mid&&rpos<=right){
                if(nums[lpos]<nums[rpos]){//没有相同数字
                    temp[cur] = nums[lpos];
                    ++lpos;
                }
                else{
                    temp[cur] = nums[rpos];
                    ++rpos;
                    pairs = (pairs+mid-lpos+1)%1000000007;
                }
            }
            else if(lpos>mid){
                temp[cur] = nums[rpos];
                ++rpos;
            }
            else if(rpos>right){
                temp[cur] = nums[lpos];
                ++lpos;
            }
            ++cur;
        }
        for(int i = left; i <= right; ++i){
            nums[i] = temp[i];
        }
        return pairs;
    }
    int InversePairs(vector<int>& nums) {
        // write code here
        vector<int> temp(nums);
        return coreCode(nums, temp, 0, nums.size()-1);
    }
};

归并排序，重点在于归并知道每次合并时左右已经有序的情况下右边哪个部分跑到前面去了。

以及注意边界位置，末尾是刚好还是后一位，统一你自己的逻辑就好，我习惯刚好。

但是一般标准库函数会是后一位。