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

链接：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;
    }