leetcode 1365. How Many Numbers Are Smaller Than the Current Number

问题来自 leetcode 1365. How Many Numbers Are Smaller Than the Current Number

---

sort以后再处理，时间复杂度是O(nlogn)

---

1, sort

class CustomComparator {
    
    public:
        bool operator()(const pair<int, int>&first, const pair<int, int>& second) {
            return first.first < second.first;
        }
};
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int size = nums.size();
        
        vector<pair<int, int>> transformed(size);
        for (int i = 0; i < size; ++i) {
            transformed[i] = {nums[i], i};
        }
        
        sort(transformed.begin(), transformed.end(), CustomComparator());
        
        vector<int> result(size);
        for (int i = 0; i < size; ++i) {             
            int val = transformed[i].first;             
            int j = i;             
            while(j >= 0 && transformed[j].first == val) {
                --j;
            }
            result[transformed[i].second] = j+1;
        }
        
        return result;
    }
};

---

2, 暴力搜索

没想到O(n^2)的暴力搜索也能过

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int size = nums.size();
        
        vector<int> result(size);
        for (int i = 0; i < size; ++i) {
            int count = 0;
            for (int j = 0; j < size; ++j) {
                if (j != i && nums[j] < nums[i])
                    ++count;
            }
            result[i] = count;
        }
        
        return result;
    }
};