315. 計算右側小于當前元素的個數
給定一個整數數組 nums，按要求返回一個新數組 counts。數組 counts 有該性質： counts[i] 的值是 nums[i] 右側小于 nums[i] 的元素的數量。
示例：
輸入：nums = [5,2,6,1]
輸出：[2,1,1,0]
解釋：
5 的右側有 2 個更小的元素 (2 和 1)
2 的右側僅有 1 個更小的元素 (1)
6 的右側有 1 個更小的元素 (1)
1 的右側有 0 個更小的元素
解題思路
使用歸并排序，每一次合并的時候，對于左區間的每個元素，根據右區間指針的位置我們可以得出，右區間存在多少個大于當前元素的（即在當前元素前已經被合并的元素個數）。
使用一個額外的index數組，記錄下每個元素在原數組的下標，使得我們可以將對應的結果加入到答案數組中
代碼
class Solution {int[] idx;int[] res;public List<Integer> countSmaller(int[] nums) {int n=nums.length;idx=new int[n];res=new int[n];for(int i=0;i<n;i++)idx[i]=i;List<Integer> list=new ArrayList<>();mergeSort(nums,0,n-1);for(int i=0;i<n;i++)list.add(res[i]);return list;}public void mergeSort(int[] nums,int l,int r){if(l<r){int mid=(r-l)/2+l;mergeSort(nums,l,mid);mergeSort(nums,mid+1,r);merge(nums,l,mid,r);}}public void merge(int[] nums,int l,int mid,int r){int i=l,j=mid+1,p=0;int[] t=new int[r-l+1];int[] ni=new int[r-l+1];while(i<=mid&&j<=r){if(nums[i]<=nums[j]){res[idx[i]]+=(j-mid-1);t[p]=nums[i];ni[p]=idx[i];p++;i++;}else {t[p]=nums[j];ni[p]=idx[j];p++;j++;}}while(i<=mid){res[idx[i]]+=(j-mid-1);t[p]=nums[i];ni[p]=idx[i];p++;i++;}while(j<=r){t[p]=nums[j];ni[p]=idx[j];p++;j++;}for(int k=0;k<r-l+1;k++){idx[k+l]=ni[k];nums[k+l]=t[k];}}
}
)
