Acwing 1238.日志统计 双指针

2024-03-30 18:28
文章标签 统计 指针 日志 acwing 1238

本文主要是介绍Acwing 1238.日志统计 双指针,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

其中每一行的格式是:

ts id  

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

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

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

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

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

输入格式

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

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

输出格式

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

每个 id 占一行。

数据范围

1≤K≤N≤1051≤105,
0≤ts,id≤1050≤,≤105,
1≤D≤100001≤≤10000

输入样例:
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例:
1
3
思路:

因为统计一定时间内是否有效,因此我们首先按照时间顺序将输入序列排序。我们使用数组id记录每个id的帖子被点赞的次数,当次数大于k时,我们将相对应的t数组下标元素改变为true,说明该id的帖子达到要求。

但是我们在考虑次数时还要考虑时间的连续性。这也是我们使用双指针的原因,维护一个区间使得该区间内的时间维持在d时间中。如果超出,我们就需要对超出部分元素的次数减1(这里可能不好理解,这个-1能进行是因为这个区间是从前向后遍历的,并且已经按照时间顺序排序。如果之前有元素超出了并且已经>=k,我们-1后不影响t数组的结果。也就是说只保留局部结果)同时将j++

代码:
package lanqiao;import java.util.*;
public class Main{public static void main(String[] args) {int[] id = new int[100000];boolean[] t = new boolean[100000];Scanner sc = new Scanner(System.in);int n = sc.nextInt();int d = sc.nextInt();int k = sc.nextInt();int[][] arr = new int[n][2];for (int i = 0; i < n; i++) {int i1 = sc.nextInt();int i2 = sc.nextInt();arr[i] = new int[]{i1,i2};}sc.close();Arrays.sort(arr,(a,b) -> (a[0] - b[0]));List<Integer> ans = new ArrayList<>();for (int i = 0, j =0; i < n; i++) {id[arr[i][1]]++;while(arr[i][0] - arr[j][0] >= d){id[arr[j][1]]--;j++;}if(id[arr[i][1]] >= k) t[arr[i][1]] = true;}for (int i = 0; i < t.length; i++) {if(t[i]) System.out.println(i);}}
}

这篇关于Acwing 1238.日志统计 双指针的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/862243

相关文章

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据(NaN值)是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值?为什么要统计空值?准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的

python logging模块详解及其日志定时清理方式

《pythonlogging模块详解及其日志定时清理方式》:本文主要介绍pythonlogging模块详解及其日志定时清理方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录python logging模块及日志定时清理1.创建logger对象2.logging.basicCo

Qt spdlog日志模块的使用详解

《Qtspdlog日志模块的使用详解》在Qt应用程序开发中,良好的日志系统至关重要,本文将介绍如何使用spdlog1.5.0创建满足以下要求的日志系统,感兴趣的朋友一起看看吧... 目录版本摘要例子logmanager.cpp文件main.cpp文件版本spdlog版本:1.5.0采用1.5.0版本主要

Mysql如何将数据按照年月分组的统计

《Mysql如何将数据按照年月分组的统计》:本文主要介绍Mysql如何将数据按照年月分组的统计方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql将数据按照年月分组的统计要的效果方案总结Mysql将数据按照年月分组的统计要的效果方案① 使用 DA

Java Optional避免空指针异常的实现

《JavaOptional避免空指针异常的实现》空指针异常一直是困扰开发者的常见问题之一,本文主要介绍了JavaOptional避免空指针异常的实现,帮助开发者编写更健壮、可读性更高的代码,减少因... 目录一、Optional 概述二、Optional 的创建三、Optional 的常用方法四、Optio

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.