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

這道題說是給了一個(gè)數(shù)組 nums，讓對(duì)于數(shù)組中的每一個(gè)數(shù)字，統(tǒng)計(jì)出數(shù)組中有多少個(gè)數(shù)小于該數(shù)字，并組成一個(gè)數(shù)組返回。參見題目中的例子不難理解題意，雖然說這是一道 Easy 的題，但是博主還是不想用 brute force 的方法，因?yàn)閷?duì)于每個(gè)數(shù)字都遍歷一遍數(shù)字統(tǒng)計(jì)小的實(shí)在是太直接了，完全不用什么思考，而且平方級(jí)的時(shí)間復(fù)雜度，也不知道 OJ 能不能放行。這道題比較好的解題思路是用時(shí)間換空間，建立每個(gè)數(shù)字與其出現(xiàn)次數(shù)之間的映射，同時(shí)按照數(shù)字大小排序，那么這里用 TreeMap 這個(gè)數(shù)據(jù)結(jié)構(gòu)就比較合適了。這樣按順序遍歷映射對(duì)兒，比當(dāng)前映射對(duì)兒的數(shù)字小的數(shù)字個(gè)數(shù)就是前面所有映射對(duì)兒的值的總和，就拿題目中的例子1來舉例吧，建立的映射對(duì)兒是：

1 -> 1
2 -> 2
3 -> 1
8 -> 1

這里定義個(gè)變量 cnt 表示當(dāng)前已經(jīng)累加的映射值，初始化為0。當(dāng)遍歷到第一個(gè)映射對(duì)兒的數(shù)字1時(shí)，當(dāng)前的 cnt 值就是比1小的數(shù)字個(gè)數(shù)，為0，是對(duì)的，然后此時(shí) cnt 要加上當(dāng)前映射值1。再遍歷到下一個(gè)映射對(duì)兒數(shù)字2，此時(shí) cnt 是比2小的數(shù)字個(gè)數(shù)，為1，是對(duì)的，然后此時(shí) cnt 要加上當(dāng)前映射值2。以此類推，就可以知道比每個(gè)數(shù)字小的數(shù)字個(gè)數(shù)了，為了方便的保存結(jié)果，這里用一個(gè) HashMap 來建立數(shù)字和比其小的數(shù)字個(gè)數(shù)之間的映射，最終組成返回?cái)?shù)組 res 的時(shí)候就直接到這個(gè) HashMap 中去取就可以了，參見代碼如下：

解法一：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int cnt = 0;
        vector<int> res;
        map<int, int> cntMap;
        unordered_map<int, int> m;
        for (int num : nums) {
            ++cntMap[num];
        }
        for (auto a : cntMap) {
            m[a.first] = cnt;
            cnt += a.second;
        }
        for (int num : nums) {
            res.push_back(m[num]);
        }
        return res;
    }
};

當(dāng)然我們也可以不用 TreeMap 和 HashMap，因?yàn)轭}目限定了數(shù)字的大小不超過 100，所以可以用一個(gè)大小為 101 的數(shù)字來代替 TreeMap，統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的個(gè)數(shù)。接下來是建立累加和數(shù)組，這樣位置i上的數(shù)字 cnt[i] 就表示不小于數(shù)字i的數(shù)字個(gè)數(shù)，所以小于數(shù)字i的數(shù)字個(gè)數(shù)就是 cnt[i-1]，有了累加和數(shù)字，就可以很方便的生成返回?cái)?shù)組 res 了，參見代碼如下：

解法二：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        vector<int> cnt(101);
        for (int num : nums) {
            ++cnt[num];
        }
        for (int i = 1; i <= 100; ++i) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) continue;
            res[i] = cnt[nums[i] - 1];
        }
        return res;
    }
};

再來看一種利用二分搜索法的解法，關(guān)于二分搜索法可以參見博主之前的總結(jié)帖 LeetCode Binary Search Summary 二分搜索法小結(jié)，先將原數(shù)組排序，這樣對(duì)于每個(gè)數(shù)字，查找第一個(gè)不小于該數(shù)字的位置，其坐標(biāo)就是數(shù)組中小于該數(shù)字的個(gè)數(shù)，還是用例子1，來舉例，排序后為 [1,2,2,3,8]，對(duì)于數(shù)字3來說，第一個(gè)不小于3的數(shù)字的位置是3，同時(shí)也表示有3個(gè)數(shù)字比數(shù)字3小，參見代碼如下：

解法三：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> res, t = nums;
        sort(t.begin(), t.end());
        for (int num : nums) {
            res.push_back(binarySearch(t, num));
        }
        return res;
    }
    int binarySearch(vector<int>& nums, int num) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < num) left = mid + 1;
            else right = mid;
        }
        return right;
    }
};

當(dāng)然我們也可以利用 C++ 的自帶函數(shù) lower_bound 來進(jìn)行二分搜索，這樣就比較偷懶啦～

解法四：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> res, t = nums;
        sort(t.begin(), t.end());
        for (int num : nums) {
            int cnt = lower_bound(t.begin(), t.end(), num) - t.begin();
            res.push_back(cnt);
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1365

類似題目：

Count of Smaller Numbers After Self

Longest Subsequence With Limited Sum

參考資料：

https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number

https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/solutions/524996/java-beats-100-o-n/

LeetCode All in One 題目講解匯總(持續(xù)更新中...)