2

给定常量整数 x 和 t，编写一个不带参数的函数，如果该函数在最后 t 秒内被调用了 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;
}

任何人都可以提出替代方案吗？

4

2 回答 2

3

您不需要保留所有先前通话的完整日志；您只需要知道最后 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 尚不清楚。

于 2012-11-25T22:36:57.867 回答
0 
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 Smith 的答案会更好，因为内存使用量具有恒定的上限。

于 2012-11-25T22:37:16.587 回答