1365. How Many Numbers Are Smaller Than the Current Number

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

1. Use 2 pointers:

//12 ms    10.4 MB
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> sorted = nums;
        int n = nums.size();
        sort(sorted.begin(), sorted.end());
        int j;
        for(int i = 0; i < n; i++){
            j = findIdx(nums[i], sorted, 0, n-1);
            nums[i] = j;
        }
        return nums;
    }
private:
    //at first, l = 0, r = list.size() - 1;
    int findIdx(int num, vector<int>& list, int l, int r){
        int m = l + (r-l) / 2;
        if(list[m] == num){
            while(m > 0){
                if(list[m-1]==list[m])
                    m--;
                else
                    break;
            }
            return m;
        } else if(list[m] > num){
            return findIdx(num, list, l, m - 1);
        } else if(list[m] < num){
            return findIdx(num, list, m + 1, r);
        }
        return m;
    }
};

2. Use STL methods:

//136 ms    10.2 MB
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> sorted = nums;
        int n = nums.size();
        sort(sorted.begin(), sorted.end());
        int dist;
        for(int i = 0; i < n; i++){
            for(vector<int>::iterator it = sorted.begin(); it != sorted.end(); it++){
                if(*it == nums[i]){
                    dist = distance(sorted.begin(), it);
                    nums[i] = dist;
                    break;
                }
            }
        }
        return nums;
    }
};