C++ solution with Divide and Conquer


  • 0
    C
    class Solution {
    public:
        void mergesort(vector<int>& nums,vector<int> &tag,int start,int mid,int end){
            if(start==end)  return;
            int k=0,st=start;
            vector<int> tg(end-start+1);
            for(int i=0;i<end-start+1;i++) tg[i]=tag[st++];
            vector<int> tp(end-start+1);
            int s1=start,e1=mid-1,s2=mid,e2=end;
            while(s1<=e1&&s2<=e2){
                if(nums[s1]<nums[s2]){
                    tp[k++]=nums[s1++];
                    tag[start+k-1]=tg[s1-start-1];
                }
                else{
                    tp[k++]=nums[s2++];
                    tag[start+k-1]=tg[s2-start-1];
                }
            }
            while(s1<=e1){
                tp[k++]=nums[s1++];
                tag[start+k-1]=tg[s1-start-1];
            }
            while(s2<=e2){
                tp[k++]=nums[s2++];
                tag[start+k-1]=tg[s2-start-1];
            }
            for(int i=0;i<k;i++)   nums[start+i]=tp[i];
        }
        void countnumber(vector<int>& nums,vector<int>& result,vector<int>& tag,int start,int end){
            if(start+1==end){ result[tag[start]]=0;return;}
            int mid=(start+end)>>1;
            countnumber(nums,result,tag,start,mid);
            countnumber(nums,result,tag,mid,end);
            int c=0,r=mid;
            for(int i=start;i<mid;i++){
                while(r<end&&nums[r]<nums[i]){
                    c++;r++;
                }
                result[tag[i]]+=c;
            }
            mergesort(nums,tag,start,mid,end-1);
        }
        
        vector<int> countSmaller(vector<int>& nums) {
            int len=(int)nums.size();
            vector<int> result(len),tag(len);
            if(len==0)  return result;
            for(int i=0;i<len;i++) tag[i]=i;
            countnumber(nums,result,tag,0,len);
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.