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;}
}