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层递归会来的快得多。