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

解题思路

先排序，后计数。

nums = [8,1,2,2,3]
//键是a[i],值是比a[i]小的数的个数。
Map<Integer,Integer> hash = new HashMap<>();
a = [1,2,2,3,8] 
int i=0;
i指向0时，比a[i]小的个数一定是0   hash.put(a[i],0);
i指向1时，比a[i]小的个数是1   hash.put(a[i],i);
i指向2时，又a[i]=a[i-1],则比a[i]小的个数是hash.get(a[i-1])   hash.put(a[i],hash.get(a[i-1]));
i指向3时，比a[i]小的个数是3   hash,put(a[i],i);

然后又遍历一遍nums数组
最终答案是[4,0,1,1,3]

相关代码

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int a[] = new int[nums.length];
        for(int i=0;i<a.length;i++) a[i] = nums[i];
        Arrays.sort(a);
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(a[0],0);
        for(int i=1;i<a.length;i++)
            if(a[i]==a[i-1])hash.put(a[i],hash.get(a[i-1]));
            else hash.put(a[i],i);
        int t[] = new int[nums.length];
        for(int i=0;i<t.length;i++) t[i] = hash.get(nums[i]);
        return t;
    }
}