分析：暴力法是可以做的但是时间复杂度O(n2)，竞赛选手很容易想到用线段树，树状数组来优化时间复杂度，这里贴几种容易理解的方法

方法一：归并排序，归并排序可以求逆序对，这是我们熟悉的，所以在归并排序的合并过程，我们可以求出右边小于当前数的有几个，这道题需要返回每个位置的右边小于它的元素数量，我们可以用一个位置数组来

　　维护位置信息，统计个数的时候直接加入到当前的位置。（思想：归并排序交换数字，改为交换位置）

class Solution {
    int[] count;
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        count = new int[n];
        List<Integer> res = new ArrayList<>();
        int[] pos = new int[n];
        for(int i = 0; i < n; i++) {
            pos[i] = i;
        }
        sort(nums,0,n-1,pos);
        for(int num : count) {
            res.add(num);
        }
        return res;
    }

    public void sort(int[] nums, int left, int right, int[] pos) {
        if(left < right) {
            int mid = (left + right) >> 1;
            sort(nums,left,mid,pos);
            sort(nums,mid+1,right,pos);
            merge(nums,left,right,mid,pos);
        }
    }
                                                            // 位置数组，交换的时候就交换位置数组
    public void merge(int[] nums, int left, int right, int mid, int[] pos) {
        int[] temp = new int[right - left + 1];
        int t = 0, l = left, r = mid + 1;
        while(l <= mid && r <= right) {
            if(nums[pos[l]] <= nums[pos[r]]) { // 这样，保证r左边到mid都是小于它的数
                count[pos[l]] += r - (mid + 1);  // 将个数加入到当前位置
                temp[t++] = pos[l++];
            } else {
                temp[t++] = pos[r++];
            }
        }
        while(l <= mid) {
            count[pos[l]] += r - (mid + 1);
            temp[t++] = pos[l++];
        }
        while(r <= right) {
            temp[t++] = pos[r++];
        }
        System.arraycopy(temp,0,pos,left,temp.length);
    }
}