leetcode 315. 计算右侧小于当前元素的个数_给一个数组,对每个元素计算该元素右侧小于该数的数量

题目

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

解析

1、给定具体的nums:[1, 3, 5, 2, 1’, 4]，当我们使用插入排序时，会发现如下特性（倒序插入）：

①[4]：移动0次；
②[1’, 4]：移动0次；
③[1’, 2, 4]：移动1次；
④[1’, 2, 4, 5]：移动3次；
⑤[1’, 2, 3, 4, 5]：移动2次；
⑥[1, 1’, 2, 3, 4, 5]：移动0次；

我们再观察，将该数列的答案手动算得的话，会得到一下的答案：

[0, 2, 3, 1, 0]

由于在插入排序时，计算移动的位置恰好等同于计算了该元素右侧小于该元素的数目，因此，我们使用该方法来进行元素数量的统计，代码如下：

public List<Integer> countSmaller(int[] nums){
   
    	List
1
2