题目描述

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints:

• 2 <= nums.length <= 500
• 0 <= nums[i] <= 100

题意：给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j的数量，其中j 满足j != i 且 nums[j] < nums[i]。

以数组形式返回答案。

算法1

(排序-哈希) $O(nlogn)$

题解1：这一题有一个显而易见的方法就是排序，然后每个数字在排序后的第一次出现的位置数组下标就是有多少个数字小于这个数字。时间复杂度$O(nlogn)$，空间复杂度$ O(n)$。

    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int n = nums.size();
        vector<int> temp,res(n);
        temp.assign(nums.begin(),nums.end());
        sort(temp.begin(),temp.end());
        unordered_map<int,int> index_hash;
        for(int i = 0 ; i < n ; i ++)
            if(i == 0 || temp[i] != temp[i - 1])
                index_hash[temp[i]] = i;
        for(int i = 0 ; i < n ; i ++)
            res[i] = index_hash[nums[i]];
        return res;
    }

算法2

(计数排序)

题解2:如果我们观察到这一题的数据范围只有0-100，那么我们可以考虑使用计数排序来做。我们统计一下每一个数字出现的次数，再使用前缀和的思想统计小于每一个数字的出现次数。这里我们回顾一下计数排序使用场景：当数据的数值范围较小，数据规模较大的情况。

    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int n = nums.size();
        vector<int> cnt(101,0),pre_cnt(101,0),res(n);
        for(int i = 0 ; i < n ; i ++)
            cnt[nums[i]] ++;
        int cur_cnt_sum = 0;
        for(int i = 0 ; i <= 100 ; i ++)
        {
            pre_cnt[i] = cur_cnt_sum;
            cur_cnt_sum += cnt[i];
        }
        for(int i = 0 ; i < n ; i ++)
            res[i] = pre_cnt[nums[i]];
        return res;
    }