Total numbers that are smaller than the current number-CodePudding

I'm trying to to find out how many numbers in the array are smaller than nums[i], for example:

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

This is what I have done:

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    vector<int> result;

    for (int i = 0; i < nums.size(); i  ) {
        int total = 0;
        for (int j = 0; j != i; j  ) {
            if (nums[j] < nums[i]) total  ;
        }
        result.push_back(total);
    }
    return result;
}

The output is:

Output: [0,0,1,1,3]

The problem is that my program ignore the first element because of my loop, and I dont't know how to fix it, can someone help me ? Thanks.

CodePudding user response：

the problem is in the inner loop, it shall loop over all elements not from 0 until current i. "for (int j = 0; j != nums.size(); j )"

CodePudding user response：

Your algorithm is O(n^2). You can do this is O(n log n) by sorting your list, then the first time each number appears you map it to its index, finally read the original (unsorted list and spit out the map values.

E.g.

Input: nums = [8,1,2,2,3]

Sorted Input: 1,2,2,3,8

map built off sorted input: {1=>0, 2=>1, 3=>3, 8=>4}

Output: [4,0,1,1,3]

CodePudding user response：

This will take nlogn time. This is how you should do it -

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    vector<int> result, tempNums=nums;

    sort(nums.begin(),nums.end());

    unordered_map<int,int>getIndex;

    for(int i = 0; i < nums.size(); i  ) {
       if(getIndex.find(nums[i]) == getIndex.end()) {
           getIndex[nums[i]]=i;
       }
    }

    for (int i = 0; i < tempNums.size(); i  ) {
        
        result.push_back(getIndex[tempNums[i]]);
    }
    return result;
}