面试算法查询
面试算法查询
提问于 2012-11-25 22:28:53
给定常量整数x和t，编写一个不带参数的函数，如果函数在最后times中被调用x次，则返回true。
这是一个可能的算法的伪代码/C++实现，但我不确定它是否正确/有效：
const int x;
const int t;
vector<long> v;
boolean countNumberOfTimesBeenCalled(){
int numberOfCallsInLastTSeconds=0;
v.push_back(System.currentTimeInMillis());
for(int x=0; x<v.size();x++){
if((v.at(x)>=(System.currentTimeInMillis()-1000*t))&&(v.at(x)<=System.currentTimeInMillis())
numberOfCallsInLastTSeconds++;
}
if(numberOfCallsInLastTSeconds==x)
return true;
else
return false;
}有人能提出其他选择吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-11-25 22:36:57
您不需要保存所有以前调用的完整日志；只需知道最后x调用跨越多长时间即可。
const int x;
const int t;
bool have_we_made_enough_calls_lately() {
static deque<int> times;
times.push_back(current_time_in_msec());
if (times.size() > x)
times.pop_front();
return times.back() - times.front() <= 1000 * t;
}编辑:在检查其他答案时，我意识到这个问题含糊不清。如果存在(至少是x调用)或确切的x调用(其他假设的调用)，则不清楚是否要返回true。
Stack Overflow用户
发布于 2012-11-25 22:37:16
bool calledXTimesInLastTSeconds() {
static deque<long> last_calls;
long time = currentTimeInMillis();
// clear last calls
long last_call_to_consider = time - 1000*t;
while (last_calls.front() < last_call_to_consider)
last_calls.pop_front()
last_calls.push_back(time);
return last_calls.size() == x;
}时间复杂度是摊销常数。
编辑:这是如何检查准确的x调用。即使您可以简单地将它更改为至少x个调用(通过将==x更改为>=x)，但是Ross的答案会更好，因为内存使用有一个固定的上限。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13556244
复制相关文章
相似问题
腾讯云开发者
