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

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

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

給你一個數(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

思路

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

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

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

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

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

代碼如下：

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

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

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

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

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

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

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

代碼如下：

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

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

publicint[]smallerNumbersThanCurrent(int[]nums){
Mapmap=newHashMap<>();//記錄數(shù)字nums[i]有多少個比它小的數(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;
}