
问题
写一个 RecentCounter 类来计算最近的请求。
它只有一个方法:ping(int t),其中 t 代表以毫秒为单位的某个时间。
返回从 3000 毫秒前到现在的 ping 数。
任何处于 [t – 3000, t] 时间范围之内的 ping 都将会被计算在内,包括当前(指 t 时刻)的 ping。
保证每次对 ping 的调用都使用比之前更大的 t 值。
输入:inputs = [“RecentCounter”,”ping”,”ping”,”ping”,”ping”], inputs = [[],[1],[100],[3001],[3002]]
输出:[null,1,2,3,3]
提示:
- 每个测试用例最多调用 10000 次 ping。
- 每个测试用例会使用严格递增的 t 值来调用 ping。
- 每次调用 ping 都有 1 <= t <= 10^9。
Write a class RecentCounter to count recent requests.
It has only one method: ping(int t), where t represents some time in milliseconds.
Return the number of pings that have been made from 3000 milliseconds ago until now.
Any ping with time in [t – 3000, t] will count, including the current ping.
It is guaranteed that every call to ping uses a strictly larger value of t than before.
Input: inputs = [“RecentCounter”,”ping”,”ping”,”ping”,”ping”], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]
Note:
- Each test case will have at most 10000 calls to ping.
- Each test case will call ping with strictly increasing values of t.
- Each call to ping will have 1 <= t <= 10^9.
示例
public class Program { public static void Main(string[] args) { var count = new RecentCounter(); Console.WriteLine(count.Ping(1)); Console.WriteLine(count.Ping(100)); Console.WriteLine(count.Ping(3001)); Console.WriteLine(count.Ping(3002)); Console.WriteLine(); var count2 = new RecentCounter2(); Console.WriteLine(count2.Ping(1)); Console.WriteLine(count2.Ping(100)); Console.WriteLine(count2.Ping(3000)); Console.WriteLine(count2.Ping(5000)); Console.ReadKey(); } public class RecentCounter { public RecentCounter() { _list = new List<int>(); } private List<int> _list = null; public int Ping(int t) { //列表法,思路简单暴力 _list.Add(t); var last = _list[_list.Count - 1]; var count = 1; for(var i = _list.Count - 2; i >= 0; i--) { if(last - _list[i] <= 3000) { count++; } else { break; } } return count; } } public class RecentCounter2 { public RecentCounter2() { _queue = new Queue<int>(); } private Queue<int> _queue = null; public int Ping(int t) { //队列法 _queue.Enqueue(t); //干掉时间差大于 3000 的,它们没有必要参与运算 while(t - _queue.Peek() > 3000) _queue.Dequeue(); return _queue.Count; } } }
以上给出2种算法实现,以下是这个案例的输出结果:
1 2 3 3 1 2 3 2
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4134。