leetcode
leetcode 851 ~ 900
最近的请求次数

最近的请求次数

难度:

标签:

题目描述

代码结果

运行时间: 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]内的请求都被计算在内的?
在使用 `bisect.bisect_left` 函数时,该函数会返回在排序列表中第一个大于等于指定值(此处为 t-3000)的元素的位置。如果列表中存在元素等于 t-3000,`bisect_left` 将返回该元素的位置;如果不存在,将返回第一个大于 t-3000 的元素的位置。这确保了我们得到的 `prev_pos` 是过去 3000 毫秒内第一个请求的位置,从而包括了所有从 t-3000 到 t 时间内的请求。
🦆
RecentCounter类中如果发生大量ping操作,列表会不断增长,这对性能有哪些潜在的影响?
随着 `RecentCounter` 类中的 `nums` 列表不断增长,两个主要的性能问题会逐渐显现:一是列表所占内存空间会持续增加,可能导致内存使用效率低下;二是每次调用 `ping(t)` 方法时,使用 `bisect_left` 进行二分查找的时间复杂度虽然是 O(log n),但随着列表长度的增加,查找效率会下降。此外,列表每次增加元素(append 操作)的时间复杂度为 O(1),但总体上要考虑查找和空间占用带来的综合性能影响。
🦆
当二分查找没有找到精确匹配t-3000的情况下,bisect_left返回的是什么位置?
当 `bisect.bisect_left` 用于查找元素 t-3000 时,如果列表中没有精确匹配的元素,该函数将返回应该插入 t-3000 以保持列表排序的位置索引。这个位置表示的是列表中第一个大于 t-3000 的元素的索引,确保了所有 t-3000 之后(包括 t-3000 时刻)的请求都被正确计算。

相关问题