leetcode_ one thousand three hundred and sixty-five

leetcode_1365 How many numbers are smaller than the current number

： Law 1
Utilization conditions each nums[i] <= 100, You can create a 101 An array of frequencies in space , Use counting sorting to calculate the frequency of each number . Then the number of digits less than the current number is the sum of all the preceding items in the frequency array with this number as the subscript .

class Solution {
    
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    
        vector<int> cnt(101);
        for(int e : nums){
     // Frequency array 
            cnt[e]++;
        }
        int sum = 0;
        vector<int> smallerThatVector(101);
        for(int i = 0; i < 101; ++i){
    
            smallerThatVector[i] += sum; // Figure out the first few items and the array 
            sum += cnt[i];  
        }
        for(int i = 0; i < nums.size(); ++i){
    
            nums[i] = smallerThatVector[nums[i]]; // And the items of the array are the answer 
        }
        return nums;
    }
};

Law two ：
utilize map Automatic sorting of . Create a tree map,key yes int,value yes vector. take nums[i] For each element in the map in , And will nums[i] Insert the corresponding in the table below vector in . So go through it again map,ans The corresponding item of the array is map Medium vector The first few are size and .

class Solution {
    
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    
      map<int, vector<int>> cnt; // Every mistake ,map Of value yes vector<int>
      for(int i = 0; i < nums.size(); ++i){
    
          cnt[nums[i]].push_back(i); // take nums[i] All insert Get into map
      }                // And will nums[i] The corresponding subscript inserts the corresponding vector<int>

      vector<int> ans(nums.size()); // Result array 
      int sum = 0;
      for(auto it = cnt.begin(); it != cnt.end(); ++it){
    
          int size = (it->second).size();
          for(int i = 0; i < size; ++i){
    
              int index = (it->second)[i]; // Get vector<int> Value , That is the 
              ans[index] = sum;     //key In the subscript corresponding to the original array .
          }
          sum += (it->second).size(); //sum Is all less than the current key The number of and 
      }
      return ans;
    }
};