1.LeetCode315题目链接
https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
2.题目解析
这个题目看起来满简单的，上手就是暴力解法，结果显而易见，超时了。
因为这个题目是计算右侧的元素，所以我们通过倒序来查找可以降低时间复杂度。首先，我们对i右侧对元素进行排序然后对比num[i],插入的位置就是我们最后的结果，直接查找的话，还是超时，看了测试数据，茫茫的多的数据，然后最后看了下评论，使用二分查找法。
public static List<Integer> countSmaller(int[] nums) {
if (nums.length == 0) {
return new ArrayList<>();
}
//用于排序之后存储数据
List<Integer> list = new ArrayList<Integer>();
int len = nums.length;
Integer[] result = new Integer[nums.length];
//可以确定最后一个位置是0
result[len - 1] = 0;
//添加最小的一个值
list.add(nums[len - 1]);
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] > list.get(list.size() - 1)) {
result[i] = list.size();
list.add(nums[i]);
} else {
//二分查找最小的值
int l = 0;
int r = list.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (nums[i] > list.get(m)) {
l = m + 1;
} else {
r = m;
}
}
list.add(r, nums[i]);
result[i] = r;
}
}
return Arrays.asList(result);
}
image
