0

我必须找出有多少其他数字小于 nums[i] 并将它们返回到另一个向量中，例如 [6,5,4,8] nums[0] = 6 所以有两个数字小于 6。所以 2将被推到另一个向量。在检查最后一个元素时我没有得到 3

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;
    }
};
4

1 回答 1

2

在条件中计数时排除第一个元素：

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

有些算法确实需要你。std::transform将一个范围的值转换为另一个范围，并count_if计算一个谓词在给定范围内返回 true 的频率：

#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 << " ";
}

使用算法的一个优点是您不必担心单个元素的索引。在上面的代码中引入与您的代码相同的错误会更加困难。换句话说，使用算法不太容易出错。尽可能考虑使用它们。

PS：您当前的方法很复杂O(N^2)。如果你对输入向量进行排序，你可以O(N log N)很容易地得到。

于 2020-09-20T09:29:20.397 回答