本文主要是介绍有多少小于当前数字的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://leetcode.cn/problems/how-many-numbers-are-smaller-than-the-current-number/description/
思路：
最简单的思路来说，就是双重for循环进行遍历，来判断个数，
优化思路，其中一个思路就是递推 + 哈希思想，哈希到数组之后，递推加起前面的所有数字，最后减去本身。
两层for循环暴力查找，时间复杂度明显为O(n^2)
那么我们来看一下如何优化。
首先要找小于当前数字的数字，那么从小到大排序之后，该数字之前的数字就都是比它小的了。
所以可以定义一个新数组，将数组排个序。
排序之后，其实每一个数值的下标就代表这前面有几个比它小的了。
用一个哈希表hash（本题可以就用一个数组）来做数值和下标的映射。这样就可以通过数值快速知道下标（也就是前面有几个比它小的）。
此时有一个情况，就是数值相同怎么办？
例如，数组：1 2 3 4 4 4 ，第一个数值4的下标是3，第二个数值4的下标是4了。
这里就需要一个技巧了，在构造数组hash的时候，从后向前遍历，这样hash里存放的就是相同元素最左面的数值和下标了。
最后在遍历原数组nums，用hash快速找到每一个数值 对应的 小于这个数值的个数。存放在将结果存放在另一个数组中。
class Solution {public int[] smallerNumbersThanCurrent(int[] nums) {int[] cnt = new int[101];int n = nums.length;for (int i = 0; i < n; i++) {cnt[nums[i]] ++;}for (int i = 1; i <= 100; i++) {cnt[i] += cnt[i - 1];}int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = nums[i] == 0 ? 0 : cnt[nums[i] - 1];}return ret;}
}public int[] smallerNumbersThanCurrent(int[] nums) {Map<Integer, Integer> map = new HashMap<>(); // 记录数字 nums[i] 有多少个比它小的数字int[] res = Arrays.copyOf(nums, nums.length);Arrays.sort(res);for (int i = 0; i < res.length; i++) {if (!map.containsKey(res[i])) { // 遇到了相同的数字，那么不需要更新该 number 的情况map.put(res[i], i);}}for (int i = 0; i < nums.length; i++) {res[i] = map.get(nums[i]);}return res;}这篇关于有多少小于当前数字的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
