1365. 有多少小于当前数字的数字

题目：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/

代码：

class Solution {

    public int[] smallerNumbersThanCurrent(int[] nums) {
        //统计0-100每个数字出现的次数
        int[] times = new int[101];
        for (int i = 0; i < nums.length; i++) {
            times[nums[i]]++;
        }
        //计算0-100中比其自身小的数字个数
        int[] mins = new int[101];
        for (int i = 1; i < mins.length; i++) {
            mins[i] = mins[i - 1] + times[i - 1];
        }
        //遍历nums，直接从mins数组取结果
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = mins[nums[i]];
        }
        return res;
    }

}

第一种解法肯定是最简单粗暴的2层循环嵌套计算即可求解，但是效率太差，这里不粘贴代码。

针对第一种解法进行优化，对于一个数字n的最终结果一定是比他小的数字结果之和；加上题目规定nums的值范围为0-100，所以我们可以进行如下操作：

1、定义一个times数组，用来统计nums中每个数字出现的次数。

2、定义一个mins数组，用来统计0-100中每个数字有多少小于当前数字的数字（相当于计算结果，只不过我们这里直接计算0-100的所有结果）

3、定义res数组，直接从mins数组取值返回

注意：重点在于2这一个步骤中，为什么我们要额外的计算0-100中每个数字有多少小于当前数字的数字呢？因为我们可以用递进的情况，对于数字n的结果有：mins[n]=比前一个数字小的数字个数+前一个数字自身出现的次数=mins[n-1]+times[n-1]。由此我们只需要3次循环遍历即可得到答案，比3层递归会来的快得多。