哈希表的神奇應(yīng)用！

1365.有多少小于當(dāng)前數(shù)字的數(shù)字

題目鏈接：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/

給你一個(gè)數(shù)組 nums，對(duì)于其中每個(gè)元素 nums[i]，請(qǐng)你統(tǒng)計(jì)數(shù)組中比它小的所有數(shù)字的數(shù)目。

換而言之，對(duì)于每個(gè) nums[i]你必須計(jì)算出有效的 j 的數(shù)量，其中 j 滿足 j != i 且 nums[j] < nums[i]?。

以數(shù)組形式返回答案。

示例 1：

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

思路

兩層for循環(huán)暴力查找，時(shí)間復(fù)雜度明顯為O(n^2)。

那么我們來(lái)看一下如何優(yōu)化。

首先要找小于當(dāng)前數(shù)字的數(shù)字，那么從小到大排序之后，該數(shù)字之前的數(shù)字就都是比它小的了。

所以可以定義一個(gè)新數(shù)組，將數(shù)組排個(gè)序。

排序之后，其實(shí)每一個(gè)數(shù)值的下標(biāo)就代表這前面有幾個(gè)比它小的了。

代碼如下：

vectorvec=nums;
sort(vec.begin(),vec.end());//從小到大排序之后，元素下標(biāo)就是小于當(dāng)前數(shù)字的數(shù)字

用一個(gè)哈希表hash（本題可以就用一個(gè)數(shù)組）來(lái)做數(shù)值和下標(biāo)的映射。這樣就可以通過(guò)數(shù)值快速知道下標(biāo)（也就是前面有幾個(gè)比它小的）。

此時(shí)有一個(gè)情況，就是數(shù)值相同怎么辦？

例如，數(shù)組：1 2 3 4 4 4 ，第一個(gè)數(shù)值4的下標(biāo)是3，第二個(gè)數(shù)值4的下標(biāo)是4了。

這里就需要一個(gè)技巧了，在構(gòu)造數(shù)組hash的時(shí)候，從后向前遍歷，這樣hash里存放的就是相同元素最左面的數(shù)值和下標(biāo)了。代碼如下：

inthash[101];
for(inti=vec.size()-1;i>=0;i--){//從后向前，記錄vec[i]對(duì)應(yīng)的下標(biāo)
hash[vec[i]]=i;
}

最后在遍歷原數(shù)組nums，用hash快速找到每一個(gè)數(shù)值 對(duì)應(yīng)的 小于這個(gè)數(shù)值的個(gè)數(shù)。存放在將結(jié)果存放在另一個(gè)數(shù)組中。

代碼如下：

//此時(shí)hash里保存的每一個(gè)元素?cái)?shù)值對(duì)應(yīng)的小于這個(gè)數(shù)值的個(gè)數(shù)
for(inti=0;i

classSolution{
public:
vector<int>smallerNumbersThanCurrent(vector<int>&nums){
vector<int>vec=nums;
sort(vec.begin(),vec.end());//從小到大排序之后，元素下標(biāo)就是小于當(dāng)前數(shù)字的數(shù)字
inthash[101];
for(inti=vec.size()-1;i>=0;i--){//從后向前，記錄vec[i]對(duì)應(yīng)的下標(biāo)
hash[vec[i]]=i;
}
//此時(shí)hash里保存的每一個(gè)元素?cái)?shù)值對(duì)應(yīng)的小于這個(gè)數(shù)值的個(gè)數(shù)
for(inti=0;ireturnvec;
}
};

publicint[]smallerNumbersThanCurrent(int[]nums){
Mapmap=newHashMap<>();//記錄數(shù)字nums[i]有多少個(gè)比它小的數(shù)字
int[]res=Arrays.copyOf(nums,nums.length);
Arrays.sort(res);
for(inti=0;iif(!map.containsKey(res[i])){//遇到了相同的數(shù)字，那么不需要更新該number的情況
map.put(res[i],i);
}
}
for(inti=0;ireturnres;
}