我在一些在线代码测验网站,其中存在复杂性限制,代码在时间和内存中不应超过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()的复杂性是不变的.
如果我是你,我会联系该网站,将他们与这个问题联系起来.
