My C++ merge sort solution as well


  • 1
    Y
    class Solution {
    public:
    
    // nums[left[i]] is the real value ,left array stores only index
    vector<int> mergerArray(vector<int> left,vector<int> right,vector<int>& nums,vector<int> &res){
        
        int lsz = left.size();
        int rsz = right.size();
        
        vector<int> re;
        
        
        int i =0 , j = 0;
        int cnt = 0;
        
        while(i<lsz && j < rsz){
            if(nums[left[i]] <= nums[right[j]]){
                re.push_back(left[i]);
                res[left[i++]] += cnt;
            }else{
                re.push_back(right[j++]);
                cnt++;
            }
        }
        while(i<lsz){
            re.push_back(left[i]);
            res[left[i++]] += cnt;
        }
        while(j < rsz){
            re.push_back(right[j++]);
        }
        return re;
    }
    
    void sortArray(vector<int>& re,vector<int>& nums,vector<int>& res){
        int sz = re.size();
        if(sz < 2) return;
        vector<int> left,right;
        left.assign(re.begin(),re.begin()+sz/2);
        right.assign(re.begin()+sz/2,re.end());
        sortArray(left,nums,res);
        sortArray(right,nums,res);
        re = mergerArray(left,right,nums,res);
        return;
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        int sz = nums.size();
        vector<int> res(sz,0);
        vector<int> re;
        for(int i=0;i<sz;i++){
            re.push_back(i);
        }
        
        sortArray(re,nums,res);
        return res;
    }
    

    };


Log in to reply
 

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