原题地址（简单）

方法1—计数排序

思路

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

代码

 复制代码
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> v(101, 0);
        int maxVal = -1;
        for(auto num : nums){
            maxVal = max(maxVal, num);
            v[num]++;
        }
        vector<int> vv(101, 0);
        for(int i=1; i<=maxVal; i++){
            vv[i] = vv[i-1] + v[i-1];
        }
        vector<int> ans;
        for(auto num : nums)
            ans.push_back(vv[num]);
        return ans;
    }
};

时空复杂度

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