給你一個數(shù)組 nums，對于其中每個元素 nums[i]，請你統(tǒng)計數(shù)組中比它小的所有數(shù)字的數(shù)目。
換而言之，對于每個 nums[i] 你必須計算出有效的 j 的數(shù)量，其中 j 滿足 j != i 且 nums[j] < nums[i] 。
以數(shù)組形式返回答案。

示例 1：
輸入：nums = [8,1,2,2,3]
輸出：[4,0,1,1,3]
解釋：
對于 nums[0]=8 存在四個比它小的數(shù)字：（1，2，2 和 3）。
對于 nums[1]=1 不存在比它小的數(shù)字。
對于 nums[2]=2 存在一個比它小的數(shù)字：（1）。
對于 nums[3]=2 存在一個比它小的數(shù)字：（1）。
對于 nums[4]=3 存在三個比它小的數(shù)字：（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 <= 500
0 <= nums[i] <= 100

這道題暴力解法兩層循環(huán)也可以，時間復(fù)雜度為O(n^2)；
所以可以用哈希表來進行優(yōu)化，

首先既然要找到小于當(dāng)前數(shù)字的個數(shù)，那么只需要把nums數(shù)組排序當(dāng)前位置之前的都是比它小的了；
這里就可以用一個哈希表，nums作為索引，下標(biāo)作為數(shù)值，這樣就可以快速找到當(dāng)前nums數(shù)的下標(biāo)，該下標(biāo)即為比當(dāng)前位置小的元素個數(shù)；

這里需要注意一點，如果nums里面有重復(fù)的元素怎么辦？
如1、2、3、4、5、5、5、5 第一個5下標(biāo)為4，最后一個5下標(biāo)為7，我們要用的肯定是下標(biāo)為4的5，所以我們在構(gòu)建hash數(shù)組時需要倒著遍歷nums；

最后只需要再遍歷原數(shù)組（排序前的），用hash快速的找到對應(yīng)小于nums的數(shù)的個數(shù)；

代碼如下：

class Solution { public:vector<int> smallerNumbersThanCurrent(vector<int>& nums) {vector<int> vec(nums);sort(vec.begin(), vec.end());vector<int> hash(101);for (int i = vec.size() - 1; i >= 0; --i) {hash[vec[i]] = i;}for (int i = 0; i < nums.size(); ++i) {vec[i] = hash[nums[i]];}return vec;} };

這道題用map當(dāng)然也可以，但是能用數(shù)組的一定優(yōu)先考慮數(shù)組，畢竟使用數(shù)組耗費的時間一定比map要少很多；

總結(jié)

以上是生活随笔為你收集整理的1365. 有多少小于当前数字的数字（哈希表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。