c – std :: count的复杂性

发布时间：2020-12-16 03:28:21 所属栏目：百科来源：网络整理

导读：我在一些在线代码测验网站,其中存在复杂性限制,代码在时间和内存中不应超过O(N),其中N是向量A的大小.我的代码完全是(完整代码)： int foo(int X,const std::vectorint A) { auto N = A.size(); auto total_hit = std::count(A.cbegin(),A.cend(),X); auto K

我在一些在线代码测验网站,其中存在复杂性限制,代码在时间和内存中不应超过O(N),其中N是向量A的大小.我的代码完全是(完整代码)：

int foo(int X,const std::vector<int> &A) {
    auto N = A.size();
    auto total_hit = std::count(A.cbegin(),A.cend(),X);
    auto K = N - total_hit;
    if (K < 0 || K >= N){
        return -1;
    }
    return K;
}

我得到了一个超出时间复杂度的结果.有没有可能而不是错？

解决方法

根据 ref：

Complexity: exactly last – first comparisons / applications of the predicate

他们错了！

并且cplusplus同意：

Complexity: Linear in the distance between first and last: Compares once each element.

当然,std::cbegin(),std::cend()和std::vector::size()的复杂性是不变的.

如果我是你,我会联系该网站,将他们与这个问题联系起来.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!