[sword finger offer] 51 Reverse pair in array

The finger of the sword Offer 51. Reverse pairs in arrays

subject

  Two numbers in an array , If the number in front is greater than the number in the back , Then these two numbers form a reverse order pair . Enter an array , Find the total number of reverse pairs in this array .

Ideas

K God's solution ：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/

Code

class Solution {
    
public:
    int reversePairs(vector<int>& nums) {
    
        vector<int>  tmp(nums.size());
        return mergeSort(0,nums.size() - 1,nums,tmp);
    }

private:
    int mergeSort(int l,int r, vector<int>& nums, vector<int>& tmp)
    {
    
        //  Termination conditions 
        if(l >= r) return 0;

        //  Recursive partition 
        int m = (l + r) / 2;
        int res = mergeSort(l,m ,nums,tmp) + mergeSort(m + 1,r ,nums,tmp);//  Merge sort 

        //  Consolidation phase 
        int i = l,j = m + 1;

        //  Save what the array looks like before merging 
        for(int k = l; k <= r; k++)
        {
    
            tmp[k] = nums[k];
        }

        for(int k = l;  k <= r; k++)
        {
    
            // m And the elements on the left are merged   Put the rest on the right into the merged array 
            if(i == m + 1)
            {
    
                nums[k] = tmp[j ++];
            }
            else if(j == r + 1 || tmp[i] <= tmp[j])
            {
    
                // m + 1 And the elements on the right are merged   Put the remaining elements on the left into the merged array 
                //  Or the elements of the array on the left are less than or equal to those on the right , Put the elements of the left array into the result array , And let the index i Add 1
                nums[k] = tmp[i ++];
            }
            else
            {
    
                //  The elements of the array on the right are smaller than those on the left , Put the elements of the array on the right into the result array , And let the index +1
                //  And at this time, the from... In the left array i To m All numbers are greater than tmp[j] Of （ Because the array on the left has been sorted ）
                nums[k] = tmp[j++];
                res += m - i + 1;//  Statistical reverse order pair 
            }
        }

        return res;
    }

};