最近的请求次数
难度:
标签:
题目描述
代码结果
运行时间: 170 ms, 内存: 21.9 MB
/*
思路:和Java解决方案类似,但利用Java Stream API来操作队列。这里不完全依赖Stream来完成任务,因为Stream更适合于处理不可变数据集,而这里我们需要对队列进行修改。
*/
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;
public class RecentCounter {
private Queue<Integer> queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.add(t);
queue = queue.stream()
.filter(time -> time >= t - 3000)
.collect(Collectors.toCollection(LinkedList::new));
return queue.size();
}
}
解释
方法:
RecentCounter 类通过使用列表来记录每次的 ping 请求时间。ping 方法被调用时,会将时间 t 添加到列表,并利用二分查找方法找出过去 3000 毫秒内(包括当前时间 t)所有的请求。使用 bisect.bisect_left 函数找出 t-3000 在列表中应插入的位置,这个位置也表示了所有在 t-3000 后发生的请求的起始位置。通过计算当前列表长度与这个位置的差,我们可以得到 t-3000 到 t 时间范围内的请求总数。
时间复杂度:
O(log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在使用bisect_left进行二分查找时,找到的位置prev_pos是如何确保所有在[t-3000, t]内的请求都被计算在内的?
▷🦆
RecentCounter类中如果发生大量ping操作,列表会不断增长,这对性能有哪些潜在的影响?
▷🦆
当二分查找没有找到精确匹配t-3000的情况下,bisect_left返回的是什么位置?
▷