CODEWITHSUNDEEP
c++vector
sadboy99
sadboy99

Reputation: 45

give how many numbers in a vector that are less than itself

i have to find how many other numbers are less than nums[i] and return them in another vector, for example [6,5,4,8] nums[0] = 6 so there is two numbers less than 6. so 2 would be pushed to the other vector. i am not getting 3 when it comes to checking the last element

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

Upvotes: 0

Views: 499

Answers (1)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122994

You exclude the first element when counting in the condition:

if(nums[j] < max && j!=0) 
               // ^^  ---- remove this

There are algorithms that do want you need. std::transform transforms one range of values to another one and count_if counts how often a predicate returns true for a given range:

#include <vector>
#include <iostream>
#include <algorithm>

std::vector<size_t> count_if_smaller(const std::vector<int>& v) {
    std::vector<size_t> result(v.size());
    std::transform(v.begin(),v.end(),result.begin(),
                [&](int x){
                    return std::count_if(v.begin(),v.end(),[&](int y){
                        return y < x;
                    });
                } );
    return result;
}

int main() {
    std::vector<int> v{6,5,4,8};
    auto r = count_if_smaller(v);
    for (auto e : r) std::cout << e << " ";
}

One advantage of using algorithms is that you need not bother about indices of single elements. Introducing the same bug as in your code would be more difficult in the above. In other words, using algorithms is less error prone. Consider to use them when you can.

PS: Your current approach has complexity O(N^2). If you sort the input vector you could get O(N log N) easily.

Upvotes: 2

Related Questions