原题地址（简单）

方法1—计数排序

思路

用计数排序来存储每个数字出现的个数。

代码

  1. class Solution {
  2. public:
  3.     vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
  4.         vector<int> v(101, 0);
  5.         int maxVal = -1;
  6.         for(auto num : nums){
  7.             maxVal = max(maxVal, num);
  8.             v[num]++;
  9.         }
  10.         vector<int> vv(101, 0);
  11.         for(int i=1; i<=maxVal; i++){
  12.             vv[i] = vv[i-1] + v[i-1];
  13.         }
  14.         vector<int> ans;
  15.         for(auto num : nums)
  16.             ans.push_back(vv[num]);
  17.         return ans;
  18.     }
  19. };

时空复杂度

时间O(N+K) K为数组中的最大值
空间O(K)