1365. How Many Numbers Are Smaller Than the Current Number

📘 題目敘述

給你一個陣列 nums，對於每個 nums[i]，請找出陣列中有多少個數字比它小。

也就是說，對每個 nums[i]，你要計算有多少個合法的 j 滿足：

• j != i
• nums[j] < nums[i]

請回傳答案陣列。

條件限制

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

🧠 解題思路

我這份寫法的想法是：

先把原本的陣列複製一份出來排序，這樣排序後每個數字前面有多少個元素，就代表有多少個數字比它小。

不過這裡要注意一件事：

• 如果有重複數字，它們的答案要一樣
• 所以不能單純看目前這個數字在排序後出現的位置
• 而是要看它第一次出現的位置

例如：

• nums = [8,1,2,2,3]
• 排序後是 [1,2,2,3,8]

這時：

• 1 第一次出現在 index 0，所以比 1 小的數字有 0 個
• 2 第一次出現在 index 1，所以比 2 小的數字有 1 個
• 3 第一次出現在 index 3，所以比 3 小的數字有 3 個
• 8 第一次出現在 index 4，所以比 8 小的數字有 4 個

所以我會先建立一個 map：

m[x] = x 在排序後第一次出現的位置

這樣這個位置值就剛好等於「有多少個數字比它小」。

最後再掃回原本的 nums，把每個 nums[i] 對應到 m[nums[i]]，就能組出答案。

也就是說，這題的核心就是：

先排序，記住每個數字第一次出現在排序陣列的 index，這個 index 就是比它小的數字個數。

所有變數

• nnums：把 nums 複製後再排序的陣列
• m：unordered_map<int, int>，記錄每個數字第一次出現在排序陣列的位置
• n：陣列長度
• ans：答案陣列

🪜 主要流程步驟

1. 先複製一份 nums 並排序

vector<int> nnums = nums;
sort(nnums.begin(), nnums.end());

這一步是整題的基礎。

因為排序之後：

• 越小的數字會排在越前面
• 某個數字第一次出現的位置，就代表前面有多少個數字比它小

所以我先保留原本的 nums，再另外開一份 nnums 來排序。

2. 建立 map，記每個數字第一次出現的位置

unordered_map<int, int> m;
int n = nums.size();
for (int i = 0; i < n; i++) {
    if (!m.count(nnums[i])) {
        m[nnums[i]] = i;
    }
}

這段的重點是：

• 我只記「第一次出現」的位置
• 因為這個位置才代表有多少個數字真的比它小

例如排序後是：

• [1,2,2,3,8]

那我記進 map 的會是：

• m[1] = 0
• m[2] = 1
• m[3] = 3
• m[8] = 4

其中 2 雖然在 index 1 和 2 都有出現，但我要的是第一次出現的位置 1，因為只有 1 個數字比 2 小。

所以這個 if (!m.count(nnums[i])) 很重要，它保證只記第一次。

3. 掃回原本的 nums，把每個數字對應到 map 裡的答案

vector<int> ans;
for (int j : nums) {
    ans.push_back(m[j]);
}

這一步是把答案組出來。

因為前面已經算好：

• 每個數字 x 有多少個數字比它小，就是 m[x]

所以現在只要照原本 nums 的順序，把對應值一個一個放進 ans 就可以了。

這樣就能保留題目要求的輸出順序。

4. 最後回傳 ans

return ans;

當所有元素都對應完成後，ans 就是答案陣列，直接回傳即可。

⏱️ 複雜度

設 n = nums.length。

• 時間複雜度：O(n log n) 排序需要 O(n log n)，後面兩次掃描與 map 查找是 O(n)，整體由排序主導。
• 空間複雜度：O(n) 額外用了複製陣列 nnums、map m，以及答案陣列 ans。

💻 程式碼實作

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> nnums = nums;
        sort(nnums.begin(), nnums.end());
        unordered_map<int, int> m;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (!m.count(nnums[i])) {
                m[nnums[i]] = i;
            }
        }
        vector<int> ans;
        for (int j : nums) {
            ans.push_back(m[j]);
        }
        return ans;
    }
};

🔗 題目連結

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