Question

362. 敲击计数器

English Version

题目描述

设计一个敲击计数器，使它可以统计在过去 5 分钟内被敲击次数。（即过去 300 秒）

您的系统应该接受一个时间戳参数 timestamp (单位为 秒 )，并且您可以假定对系统的调用是按时间顺序进行的(即 timestamp 是单调递增的)。几次撞击可能同时发生。

实现 HitCounter 类:

• HitCounter() 初始化命中计数器系统。
• void hit(int timestamp) 记录在 timestamp ( 单位为秒 )发生的一次命中。在同一个 timestamp 中可能会出现几个点击。
• int getHits(int timestamp) 返回 timestamp 在过去 5 分钟内(即过去 300 秒)的命中次数。

 

示例 1:

输入：
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
输出：
[null, null, null, null, 3, null, 4, 3]

解释：
HitCounter counter = new HitCounter();
counter.hit(1);// 在时刻 1 敲击一次。
counter.hit(2);// 在时刻 2 敲击一次。
counter.hit(3);// 在时刻 3 敲击一次。
counter.getHits(4);// 在时刻 4 统计过去 5 分钟内的敲击次数, 函数返回 3 。
counter.hit(300);// 在时刻 300 敲击一次。
counter.getHits(300); // 在时刻 300 统计过去 5 分钟内的敲击次数，函数返回 4 。
counter.getHits(301); // 在时刻 301 统计过去 5 分钟内的敲击次数，函数返回 3 。

 

提示:

• 1 <= timestamp <= 2 * 109
• 所有对系统的调用都是按时间顺序进行的（即 timestamp 是单调递增的）
• hit and getHits 最多被调用 300 次

 

进阶: 如果每秒的敲击次数是一个很大的数字，你的计数器可以应对吗？

解法

方法一

class HitCounter:
  def __init__(self):
    """
    Initialize your data structure here.
    """
    self.counter = Counter()

  def hit(self, timestamp: int) -> None:
    """
    Record a hit.
    @param timestamp - The current timestamp (in seconds granularity).
    """
    self.counter[timestamp] += 1

  def getHits(self, timestamp: int) -> int:
    """
    Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in seconds granularity).
    """
    return sum([v for t, v in self.counter.items() if t + 300 > timestamp])


# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)

class HitCounter {

  private Map<Integer, Integer> counter;

  /** Initialize your data structure here. */
  public HitCounter() {
    counter = new HashMap<>();
  }

  /**
     Record a hit.
    @param timestamp - The current timestamp (in seconds granularity).
   */
  public void hit(int timestamp) {
    counter.put(timestamp, counter.getOrDefault(timestamp, 0) + 1);
  }

  /**
     Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in seconds granularity).
   */
  public int getHits(int timestamp) {
    int hits = 0;
    for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
      if (entry.getKey() + 300 > timestamp) {
        hits += entry.getValue();
      }
    }
    return hits;
  }
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */

use std::{ collections::BinaryHeap, cmp::Reverse };

struct HitCounter {
  /// A min heap
  pq: BinaryHeap<Reverse<i32>>,
}

impl HitCounter {
  fn new() -> Self {
    Self {
      pq: BinaryHeap::new(),
    }
  }

  fn hit(&mut self, timestamp: i32) {
    self.pq.push(Reverse(timestamp));
  }

  fn get_hits(&mut self, timestamp: i32) -> i32 {
    while let Some(Reverse(min_elem)) = self.pq.peek() {
      if *min_elem <= timestamp - 300 {
        self.pq.pop();
      } else {
        break;
      }
    }

    self.pq.len() as i32
  }
}