315. Count of Smaller Numbers After Self
常规暴力破解解法：

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> res;
        for(int i = 0;i < n;i++)
        {
            int cnt = 0;
            for(int j = i +1;j < n;j++)
            {
                if(nums[j] < nums[i])
                    cnt++;
            }
            res.push_back(cnt);
        }
        
        return res;
    }
};

我们可以看到执行结果：Time Limit Exceeded：

Time Limit Exceeded
Details 
Last executed input
[-6099,-9852,3693,-1261,2532,9843,-9407,5514,-6370,-7983,-6693,-3308,1232,-9310,-1156,-
View All

Count Inversions in an array

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        res.resize(n);
        vector<int> sorted = nums;
        helper(nums,sorted,0,n-1);
        
        return res;
    }
private:
    vector<int> res;
    void helper(const vector<int>& nums,vector<int>& sorted,int a,int b)
    {
        if(a >=b) return;
        int mid = a + (b-a)/2;
        helper(nums,sorted,a,mid);
        helper(nums,sorted,mid+1,b);
        
        for(int i = a;i <= mid;i++)
        {
            vector<int>::iterator iter=lower_bound(sorted.begin()+mid+1,sorted.begin()+b+1,nums[i]);
            res[i] += iter - (sorted.begin() + mid + 1);
        }
        
        sort(sorted.begin() + a,sorted.begin()+b+1);
    }
};

运行结果:

Runtime: 664 ms, faster than 10.05% of C++ online submissions for Count of Smaller Numbers After Self.
Memory Usage: 74.3 MB, less than 26.45% of C++ online submissions for Count of Smaller Numbers After Self.

这里存在一个可以优化的点，排序的时候我们没有必要调用sort复杂度nlogn，可以使用归并排序。优化后的代码如下：

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        res.resize(n);
        vector<int> sorted = nums;
        helper(nums,sorted,0,n-1);
        
        return res;
    }
private:
    vector<int> res;
    void helper(const vector<int>& nums,vector<int>& sorted,int a,int b)
    {
        if(a >=b) return;
        int mid = a + (b-a)/2;
        helper(nums,sorted,a,mid);
        helper(nums,sorted,mid+1,b);
        
        for(int i = a;i <= mid;i++)
        {
            vector<int>::iterator iter=lower_bound(sorted.begin()+mid+1,sorted.begin()+b+1,nums[i]);
            res[i] += iter - (sorted.begin() + mid + 1);
        }
        
        vector<int> temp(b-a+1);
        int i = a,j = mid+1,p = 0;
        while(i <= mid && j <= b)
        {
            if(sorted[i] <= sorted[j])
            {
                temp[p++] = sorted[i++];
            }else{
                temp[p++] = sorted[j++];
            }
        }
        
        while(i <= mid)
        {
            temp[p++] = sorted[i++];
        }
        
        while(j <= b)
        {
            temp[p++] = sorted[j++];
        }
        
        for(int i = 0;i < b-a+1;i++)
            sorted[a+i] = temp[i];
    }
};

运行效率：

Runtime: 744 ms, faster than 8.31% of C++ online submissions for Count of Smaller Numbers After Self.
Memory Usage: 173.9 MB, less than 10.23% of C++ online submissions for Count of Smaller Numbers After Self.

非常奇怪的是运行效率反而变差了？
这里讲道理是将排序的时间复杂度从O(nlogn)变为O(n)，讲道理运行效率应该提高才对。