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

示例:

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

哇的一声就哭了出来，这其实是逆序对的变型。
归并排序的基础上加上一个小小的统计就完成任务了。
值得学习的是分治法解决问题的思路。
将原问题分解成了两个子问题，并且分解子问题后还可以根据子问题合并出原问题的解。

毕竟对于左半部分的每个元素的来说，在只考虑右半部分的元素中，右半部分元素是否有序是无关紧要的，而且如果有序的话，更方便。

那么问题就可以通过分治法来解决了。

这里还有一个小技巧，就是通过对索引数组进行排序，来方便的找到归并排序中当前元素对应的原数组元素。就像是一个指针数组一样，根据指针指向的元素的值来修改指针的相对位置。

代码

class Solution {
   
public:
    void merge(vector<int>& nums, vector<int>& index, vector<int>& tmp, int left, int right, vector<int>& ans) {
   
        if (left >= right) return; 
        int mid = (left + right) / 2;
        merge(nums, index, tmp, left , mid, ans);
        merge(nums, index, tmp, mid + 1 , right, ans);
        
        int l = left, r = mid + 1,i = left;
        while (l <= mid || r <= right) {
   
            if (r > right || (l <= mid && (nums[index[l]] <= nums[index[r]]))) {
   
                tmp[i++] = index[l];
                ans[index[l]] += (r - mid - 1);
                l++;
            } else {
   
                tmp[i++] = index[r++];
            }
        }
        for (int i = left; i <= right; i ++) index[i] = tmp[i];
    }
    vector<int> countSmaller(vector<int>& nums) {
   
        int N = nums.size();
        
        vector<int> index (N), tmp (N), ans (N, 0);
        for (int i = 0; i < N; i++) index[i] = i;
        
        merge(nums, index, tmp, 0, N - 1, ans);
        return ans;
    }
};