算法-双指针、BFS与图论-1238. 日志统计

题目

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格式是：

ts id  

表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D的时间段内收到不少于 K个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式

第一行包含三个整数 N,D,K。

以下 N 行每行一条日志，包含两个整数 ts和 id。

输出格式

按从小到大的顺序输出热帖 id。

每个 id占一行。

数据范围

1≤K≤N≤105,
0≤ts,id≤105,
1≤D≤10000

输入样例：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例：

1
3

思路

1. 暴力搜索：

   1. # 第一种循环方式
      for id :
          for ts ：
      # 第二种循环方式
      for （时间段）：
          # 统计时间段内每个id点赞的数量
          cnt[N]={0} # 清空的作用
          for (id)：
              cnt[id]++
              if cnt[id]>=k :
                  st[id]=true
      

2. 优化：对于相邻的两个时间区间，只有开头i和结尾j不一样，所以可以把开头去掉，结尾加上：cnt[id[i]]--;cnt[id[j]]++;==》双指针
3. AcWing 1238. 日志统计 - AcWing

代码

N = 100000  # ID的最大值是99999，列表长度是N+1，因为索引是从0开始的  
logs = []  # 存储日志的列表  
st = [False] * (N + 1)  # 标记热帖的列表，长度应为N+1  
cnt = [0] * (N + 1)  # 记录每个ID的赞数，长度应为N+1  
  
# 读取n, d, k的值  
n, d, k = map(int, input().split())  
  
# 读取日志并存储到列表中  
for _ in range(n):  
    time, id_num = map(int, input().split())  
    logs.append((time, id_num)) # 把每条的日志作为元组append
  
# 根据时间排序日志  
logs.sort(key=lambda x: x[0])  
  
# 双指针算法  
i, j = 0, 0  
while i < n:  
    t = logs[i][1]  # 当前日志的ID  
    cnt[t] += 1  # 为当前ID增加赞数  
  
    # 如果当前日志与最早日志的时间差超过了d，最早的赞过期  
    while i > j and logs[i][0] - logs[j][0] >= d:  
        cnt[logs[j][1]] -= 1  # 过期的赞作废  
        j += 1  # 移动j指针  
  
    # 如果某个ID的赞数达到或超过k，标记为热帖  
    if cnt[t] >= k:  
        st[t] = True  
  
    i += 1  
  
# 遍历ID，输出热帖的ID  
for i in range(0, N):  # 从1开始遍历，因为ID是从1开始的  
    if st[i]:  
        print(i)