题目: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中每个数字
mins[n-1]+times[n-1]。由此我们只需要3次循环遍历即可得到答案,比3层递归会来的快得多。