题解 | 数组中的逆序对

class Solution {
public:
    /**
        一个数比后面的某一个数大则就是一个逆序对，计数就加1；
        暴力检测每个数N^2,利用分治算法，从下往上时，计数同时进行排序原数组，因为数组有序减少了比较时间
     */
    int count = 0;
    int const mod = 1000000007;

    int InversePairs(vector<int>& nums) {
        int n = nums.size();
        if(n<2)return 0;

        dp(nums, 0, nums.size()-1);
        
        return count; 
    }

    void dp(vector<int>& nums, int left, int right){
        if(left >= right) return;

        int mid = left + (right-left)/2;

        dp(nums, left, mid);

        dp(nums, mid+1, right);  //两边排好了序

        vector<int> temp;
        int l_vec=left, r_vec=mid+1; //进行检测，并排序
        while(l_vec <= mid && r_vec <=right){
            if(nums[l_vec] > nums[r_vec]){  //当前是逆序对
                count += mid - l_vec + 1;
                count %= mod;
                temp.push_back(nums[r_vec]);  //把小的放入，进行排序
                r_vec++;
            }else{  //当前不是逆序对
                temp.push_back(nums[l_vec]);  
                l_vec++;
            }
        }

        while(l_vec <=mid){ //如果左数组剩余
            temp.push_back(nums[l_vec] );
            l_vec++;
        }

        while(r_vec <= right){
            temp.push_back(nums[r_vec]);
            r_vec++;
        }

        int index = left;
        //排好序之后改变其原来的数组
        for(int num:temp){
            nums[index] = num;
            index++;
        }
    }



};