哈希表的神奇應用！

1365.有多少小于當前數字的數字

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

給你一個數組 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 <= 500
• 0 <= nums[i] <= 100

思路

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

那么我們來看一下如何優化。

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

所以可以定義一個新數組，將數組排個序。

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

代碼如下：

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

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

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

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

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

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

最后在遍歷原數組nums，用hash快速找到每一個數值 對應的 小于這個數值的個數。存放在將結果存放在另一個數組中。

代碼如下：

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

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

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