315. 计算右侧小于当前元素的个数

315. 计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

method: 归并数组索引的同时计算左侧数组上的元素的count值

int cnt(vector<int>& nums, int st, int ed, int key,vector<int>& pos){
        // //降序排列，返回比k小的元素的个数
        if(st>ed)return 0;
        int mid=(st+ed)/2;
        if(nums[pos[mid]]>=key)return cnt(nums,mid+1,ed,key,pos);
        else return ed-mid+1+cnt(nums,st,mid-1,key,pos);
    }
    void merge(vector<int> &arr,int L,int mid,int R, vector<int>& pos, vector<int>& dp ){
        for(int i=L;i<=mid;i++){
            dp[pos[i]]+=cnt(arr,mid+1,R,arr[pos[i]],pos);
        }
        vector<int> help(R-L+1,0);
        //nt *help = new int[];
        int p1=L,p2=mid+1,i=0;
        while(p1<=mid && p2<=R)
        {
            help[i++] = arr[pos[p1]]<arr[pos[p2]] ? pos[p2++] : pos[p1++];
        }
        while(p1<=mid)
            help[i++] = pos[p1++];
        
        while(p2<=R)
            help[i++] = pos[p2++];
        
        for (int i=0;i<R-L+1;i++)
        {
            pos[L+i] = help[i];
        }
    }
    void sortprocess(vector<int> &arr,int L,int R, vector<int>& pos, vector<int>& dp)
    {
        if (L < R)
        {
            int mid = L + ((R-L)>>2);  //  (L+R)/2
            sortprocess(arr,L,mid,pos,dp);
            sortprocess(arr,mid+1,R,pos,dp);
            merge(arr,L,mid,R,pos,dp);
        }
    }
 
    void MergeSort(vector<int> &arr,int L,int R, vector<int>& pos, vector<int>& dp)
    {
        if (arr.size()<2)
            return;
        sortprocess(arr,L,R,pos,dp);
    }
    vector<int> countSmaller(vector<int>& nums) {
        int n=nums.size();
        if(n==0)return vector<int>();
        vector<int> pos(n,0);
        for(int i=0;i<n;i++)
            pos[i]=i;
        vector<int> dp(n,0);
        MergeSort(nums,0,n-1,pos,dp);
        return dp;
    }