1365. 有多少小于当前数字的数字
难度简单111
给你一个数组
nums，对于其中每个元素nums[i]，请你统计数组中比它小的所有数字的数目。换而言之，对于每个
nums[i]你必须计算出有效的j的数量，其中j满足j != i且nums[j] < nums[i]。以数组形式返回答案。
示例 1：
输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3] 解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 对于 nums[1]=1 不存在比它小的数字。 对于 nums[2]=2 存在一个比它小的数字：（1）。 对于 nums[3]=2 存在一个比它小的数字：（1）。 对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。示例 2：
输入：nums = [6,5,4,8] 输出：[2,1,0,3]示例 3：
输入：nums = [7,7,7,7] 输出：[0,0,0,0]
提示：
2 <= nums.length <= 5000 <= nums[i] <= 100
可以直接想到得是：O(n^2)
class Solution {// 最基础的办法：两重循环，为每个数遍历一次数组，统计比他小的数的个数public int[] smallerNumbersThanCurrent(int[] nums) {int[] rs=new int[nums.length];for(int i=0;i<rs.length;i++){for(int j=0;j<rs.length;j++){if(nums[j]<nums[i]){rs[i]++;}}}return rs;}
}但是看了下元素范围，我发现事情没那么简单：
元素范围在[0,100]，可以联想到利用索引实现哈希表，但是没有直接想到解法，不过看了下题解，有两个做法倒是很合适本题：
1.quick select，每次都能将一个元素放到他应该在的位置，他左边的都是比它小的
2.计数排序：计算每个数出现的次数，然后计算前缀和：
8 1 2 2 3
0 1 2 3 4 5 6 7 8 9 ...
1 2 1 1
0 1 3 4 5
首先附上第二种解法的代码：
class Solution {public int[] smallerNumbersThanCurrent(int[] nums) {// 记下每个数字出现的次数，因为数组元素范围是[0,100]，所以数组大小为101int[] cnt = new int[101];// 计数for (int i : nums) {cnt[i]++;}int[] preSum = new int[cnt.length];preSum[0] = cnt[0];// 计算cnt的前缀和：也就是小于等于该数的数出现的次数for (int i = 1; i < cnt.length; i++) {preSum[i] = preSum[i - 1] + cnt[i];}int[] rs = new int[nums.length];// 前缀和还需要减去该数自己出现的次数，才是小于该数的数出现的次数for (int i = 0; i < rs.length; i++) {rs[i] = preSum[nums[i]] - cnt[nums[i]];}return rs;}public static void main(String[] args) {int[] a = {8, 1, 2, 2, 3};new Solution().smallerNumbersThanCurrent(a);}
}
然后是quick select，又复习一遍partition函数：
emmm 看了下 好像不是用quick select ，而是单纯排序，之后再统计
（不过确实复习了一下快排