题目大意：
计算右侧小于当前元素的个数
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=315
解题思路分析：
如果本题使用暴力解，感觉会超时，因此并没有尝试。看了题目的提示后才发现比较高效的方法是使用二分查找。我们从数组末尾开始向前循环遍历每个数字，循环时，将当前数字插入到一个新的List中，插入时使用二分查找，找到第一个大于等于当前数字的下标，并将其插入到那个下标处，此时数组能够保证升序排列，因此当前下标前的数字个数即是比当前数字小的所有数字个数。
实现代码：
public List<Integer> countSmaller(int[] nums) {
// 返回结果
List<Integer> res=new ArrayList<>();
// 数组长度为0，直接返回
if(nums.length==0) return res;
// 为了提高效率，新建一个数组型的返回结果
int[] arr=new int[nums.length];
// 新建一个list，用于排序
List<Integer> list=new ArrayList<>();
// 从数组最后一位开始向前循环
for(int i=nums.length-1;i>=0;i--){
// 当前数字
int num = nums[i];
// 将当前数字插入到新建list中
// 使用二分查找找到插入位置
int left=0,right=list.size()-1;
while(left<=right){
int mid=(left+right)/2;
if(num<=list.get(mid)) right=mid-1;
else left=mid+1;
}
// 将当前数字插入到相应位置，保证list升序排列
list.add(left, num);
// 当前位置前所有数字均小于当前数字，将个数加入返回结果
arr[i]=left;
}
// 将list转化为数组
for(int count : arr) res.add(count);
return res;
}本题解法执行时间为16ms。
Runtime: 16 ms, faster than 39.97% of Java online submissions for Count of Smaller Numbers After Self.
Memory Usage: 38.3 MB, less than 100.00% of Java online submissions for Count of Smaller Numbers After Self.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-315-count-of-smaller-numbers-after-self-解题思路分析/