51. reverse order pairs in the array

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

Ideas ： Merge sort

• Termination conditions ：l>=r when , return 0
• Recursive partition ： Calculate the midpoint of the array m, Recursively divide the left subarray and the right subarray ;
  • Merge and reverse pair Statistics ：
    • Temporary array nums Closed interval [l,r] To auxiliary array tmp
    • Cyclic merger ： Set the double pointers to point to the first element of the right sub array respectively ：
      • When i==m+1 when , Represents that the left sub array has been merged , Add right subarray , And implement j++
      • otherwise , When j==r+1 perhaps tmp[i]<=tmp[j] when , Represents that the right sub array has been merged or the current element of the left sub array is smaller than the current element of the right sub array , Add the left sub array and execute i++
      • otherwise , When tmp[i]>tmp[j] when , Represents that the current element of the left sub array is greater than the current element of the right sub array , Add the right sub array and execute j++, At this time, the reverse order pair is formed m-i+1, Add to res
• return res

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

    int mergeSort(int l,int r,vector<int>& nums,vector<int>& tmp){
        if(l>=r) return 0;
        int m=l+r>>1;
        int res=mergeSort(l,m,nums,tmp)+mergeSort(m+1,r,nums,tmp);

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

        int i=l,j=m+1,k=l;
        while(k<=r){
            if(i==m+1)
                nums[k++]=tmp[j++];
            else if(j==r+1||tmp[i]<=tmp[j]){
                nums[k++]=tmp[i++];
            }
            else{
                nums[k++]=tmp[j++];
                res+=m-i+1;
            }
        }
        return res;
    }
};

Time complexity O(nlogn)

Spatial complexity O(n)