日志统计(每日一题)

日志统计(每日一题)

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

其中每一行的格式是：

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

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

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

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

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

输入格式 第一行包含三个整数 ,D,K。

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

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

每个 id 占一行。

数据范围 1≤K≤≤105, 0≤ts,id≤105, 1≤D≤10000 输入样例： 7 10 2 0 1 0 10 10 10 10 1 9 1 100 100 输出样例： 1

提交代码： C++

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
ct int  = 100010;
int n, d, k;
int cnt[];
PII logs[]; // 存放每时刻的点赞情况
bool st[]; // 记录每个帖子是否是热帖

int main()
{
    scanf ("%d%d%d", &n, &d, &k);
    for (int i = 0; i < n; ++ i) scanf("%d%d", &logs[i].x, &logs[i].y);
    sort(logs, logs + n);
    for (int i = 0, j = 0; i < n; ++ i)
    {
        int id = logs[i].y; // 这个时刻这这个id被点赞了
        cnt[id] ++; // 然后这个人对应的cnt++
        while(logs[i].x - logs[j].x >= d) // 如果区间【j, i】长度大于等于d
                                          // 就需要把前面多余的区间的cnt--
        {
            cnt[logs[j].y] --; // 把前面加了的再减回来
            j ++;
        }
        if (cnt[id] >= k) st[id] = true; // 如果在不大于d区间以内可以满足要求 则为true
    }
    for (int i = 0; i <= 100000; ++ i)
    {
        if(st[i]) printf("%d\n", i); // 因为这里的id的范围说出来了 所以可以一个个看 那些符合要求
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main
{
	static int  = 100010;
	static int n, d, k;
	static int [] cnt = new int [];
	static PII [] logs = new PII [];
	static boolean [] st = new boolean [];
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String [] strs = reader.readLine().split(" ");
		n = Integer.parseInt(strs[0]);
		d = Integer.parseInt(strs[1]);
		k = Integer.parseInt(strs[2]);
		for (int i = 0; i < n; ++ i)
		{
			strs = reader.readLine().split(" ");
			int t = Integer.parseInt(strs[0]);
			int id = Integer.parseInt(strs[1]);
			logs[i] = new PII(t, id);
		}
		Arrays.sort(logs, 0, n);
		for(int i = 0,j = 0;i < n;i++)
       {
           cnt[logs[i].id] ++;
           while(logs[i].t - logs[j].t >= d)
           {
               cnt[logs[j].id] --;
               j ++; // 先减了之后才能++
           }
           if(cnt[logs[i].id] >= k) st[logs[i].id] = true; 
       }
		for(int i = 0; i <= 100000; ++ i)
		{
			if (st[i]) println(i);
		}
	}
	
	public static class PII implements Comparable<PII>
	{
		int t;
		int id;
		public PII (int t, int id)
		{
			 = t;
			this.id = id;
		}
		@Override
		public int compareTo(PII o) {
			// TODO Auto-generated method stub
			return Integerpare(t, );
		}
		
	}
}

Python

 = 100010

if __name__ == '__main__':
    n, d, k = map(int, input().split())
    logs, cnt, st = [], [0]*, [0]*
    for _ in range(n): logs.append([int(x) for x in input().split()])
    logs.sort()

    i, j = 0, 0
    while i<n:
        ts, id = logs[i]
        cnt[id] += 1
        while ts-logs[j][0]>=d:
            cnt[logs[j][1]] -= 1
            j += 1
        if cnt[id]>=k: st[id] = 1
        i += 1

    for i in range():
        if st[i]: print(i)