题目描述：给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质：
counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。
eg:
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.思路描述：暴力解法就不写了，会超时，
class Solution {
private int[] counters;
private int[] tmps;
private int[] indexs;
public List<Integer> countSmaller(int[] nums) {
if (nums == null) return null;
List<Integer> res = new ArrayList<>();
if (nums.length == 0) return res;
int Len = nums.length;
counters = new int[Len];
tmps = new int[Len];
indexs = new int[Len];
for (int i = 0; i < Len; i ++) {
indexs[i] = i;
}
mergeSort(nums, 0, Len - 1);
for (int i = 0; i < nums.length; i ++) {
res.add(counters[i]);
}
return res;
}
//归并排序
private void mergeSort(int[] nums, int l, int r) {
if (l == r) return;
int m = l + (r - l)/2;
mergeSort(nums, l, m);
mergeSort(nums, m + 1, r);
if (nums[indexs[m]] > nums[indexs[m + 1]]) {
mergeTwoSortArray(nums, l, r, m);
}
}
//子排序
private void mergeTwoSortArray(int[] nums,int l,int r,int mid) {
for (int i = l; i <= r;i++) {
tmps[i] = indexs[i];
}
int i = l;
int j = mid + 1;
for (int k = l; k <= r; k ++) {
if (i > mid) {
indexs[k] = tmps[j];
j ++;
}else if(j > r) {
indexs[k] = tmps[i];
i ++;
counters[indexs[k]] += (r - mid);
}else if(nums[tmps[i]] <= nums[tmps[j]]) {
indexs[k] = tmps[i];
i++;
counters[indexs[k]] += (j - mid - 1);
}else {
indexs[k] = tmps[j];
j++;
}
}
}
}