算法分析
排序+双指针
-
1、对所有的赞按照时间从小到大排序
-
2、通过双指针
i
,j
维护长度不大于d
的区间,并记录该区间的中所有帖子获得的赞数
时间复杂度 $O(nlogn)$
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 100010;
static PIIs[] logs = new PIIs[N];
static int[] cnt = new int[N];
static boolean[] st = new boolean[N];
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = reader.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int d = Integer.parseInt(s1[1]);
int k = Integer.parseInt(s1[2]);
for(int i = 0;i < n;i++)
{
String[] s2 = reader.readLine().split(" ");
int t = Integer.parseInt(s2[0]);
int id = Integer.parseInt(s2[1]);
logs[i] = new PIIs(t,id);
}
Arrays.sort(logs,0,n);
for(int i = 0,j = 0;i < n;i++)
{
int id = logs[i].id;
cnt[id] ++;
while(logs[i].t - logs[j].t >= d)
{
cnt[logs[j].id] --;
j ++;
}
if(cnt[id] >= k) st[id] = true;
}
for(int i = 0;i <= 100000;i++)
{
if(st[i])
System.out.println(i);
}
}
}
class PIIs implements Comparable<PIIs>
{
public int t;
public int id;
public PIIs(int t,int id)
{
this.t = t;
this.id = id;
}
@Override
public int compareTo(PIIs o) {
// TODO 自动生成的方法存根
return Integer.compare(t, o.t);
}
}
我想问,
这里面的t 和o.t 有什么不同吗,区别是什么啊
请问PIIs必须通过这个接口实现吗,我去掉了这个接口后发现排序那行报错了,大佬能给蒟蒻指点一下吗
对啊,因为系统里面没有这个排序
为什么需要进行sort排序呢?如果说是为了从小到大遍历id号码,那么最后输出时的for循环不是可以保证从小到大输出吗?求大佬解答
????????
这个我懂了,是为了对时间进行排序
妙啊~~~群友 爱了爱了
cnt[logs[j].id] –;
j ++; 为什么cnt[logs[j].id]– ,为什么里面是logs[j]而不是logs[i]
i
在前面走,j
跟着后面走,i
和j
维护长度不大于d
的区间,若超过了d
,则j
前进进行区间回缩明白了 谢谢
while(logs[i].t - logs[j].t >= d)还有这里,i不是在j的前面吗 这样子相减不就成了负数???
i
在前面走,j
跟着后面走,所有i
在j
的前,相减一定是正数啊