AcWing 1238. 日志统计（Java 两种解法）    原题链接    中等

作者： 作者的头像   j简单 ,  2021-03-01 18:33:20 ,  所有人可见 ,  阅读 591

4


4

【题目描述 】
在这里插入图片描述
在这里插入图片描述

AcWing 1238. 日志统计

解法一

【思路】
排序 枚举

1、 对日志记录按（id，时间）升序排序
2 、遍历日志记录，最低要求：至少与当前第i条记录相距为 K - 1的那条记录也要是相同id且时间范围在D内


import java.io.*;
import java.lang.Math;
import java.util.Arrays;
class blog implements Comparable<blog>{
    int id, ts;
    public blog (int idd, int tss){
        id = idd;
        ts = tss;
    }
    //按(id,时间)升序排序
    public int compareTo(blog o){
        if(this.id == o.id) return this.ts - o.ts; //id相同则按时间排序
        else return this.id - o.id;
    }
    public String toString(){
        return this.id+" "+ this.ts +" \n";
    }

}

public class Main{
    static int N = 100010;
    static blog[] q= new blog[N];
    static boolean[] st = new boolean[N];
    static int [] cnt = new int[N];

    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s[] = bf.readLine().split(" ");
        int n = Integer.parseInt(s[0]), D = Integer.parseInt(s[1]), K = Integer.parseInt(s[2]);

        for(int i = 0; i < n; i ++){
            String data[] = bf.readLine().split(" ");
            int a = Integer.parseInt(data[0]);
            int b = Integer.parseInt(data[1]);
            q[i] = new blog(b,a);
        }
        Arrays.sort(q, 0, n);


        for(int i = 0; i < n; i ++){
            //最低要求：至少第next条记录也要是相同id且时间范围在D内
            int next = i + K - 1;
            if(next >= n) continue;
            int id = q[next].id;
            int t = q[next].ts;
            if(next < n && id == q[i].id && t - q[i].ts < D)
                st[id] = true;
        }

        for(int j =0; j < N; j ++)
            if(st[j]) System.out.println(j);



    }
}

解法二

【思路】
双指针

1、 对日志记录按（时间，id）升序排序
2 、for(时间段)
在枚举该时间段内的所有id时存在重复计算的区间，使用双指针进行优化


import java.io.*;
import java.lang.Math;
import java.util.Arrays;
class blog implements Comparable<blog>{
    int id, ts;
    public blog (int idd, int tss){
        id = idd;
        ts = tss;
    }
    //按时间升序排序
    public int compareTo(blog o){
        if(this.ts == o.ts) return this.id - o.id;
        else return this.ts - o.ts;
    }
    public String toString(){
        return this.ts +" "+this.id+" \n";
    }

}

public class Main{
    static int N = 100010;
    static blog[] q= new blog[N];
    static boolean[] st = new boolean[N];
    static int [] cnt = new int[N];

    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s[] = bf.readLine().split(" ");
        int n = Integer.parseInt(s[0]), D = Integer.parseInt(s[1]), K = Integer.parseInt(s[2]);

        for(int i = 0; i < n; i ++){
            String data[] = bf.readLine().split(" ");
            int a = Integer.parseInt(data[0]);
            int b = Integer.parseInt(data[1]);
            q[i] = new blog(b,a);
        }
        Arrays.sort(q, 0, n);
        //双指针 i在前 j在后 
        for(int i =0, j = 0; i < n; i ++){
            int id = q[i].id;
            cnt[ id ]++;
            while( q[i].ts - q[j].ts >= D){//两个时间差大于K j则要追上
                cnt[ q[j].id ] --;
                j ++;
            }
            if(cnt[id] >= K ) st[id] = true;

        }

        for(int j =0; j < N; j ++)
            if(st[j]) System.out.println(j);



    }
}

4 评论

用户头像
心安_7   13天前         踩      回复

佬能看看我哪里错了吗？

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n, k, d;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        d = scanner.nextInt();
        k = scanner.nextInt();
        Pair pair[] = new Pair[100010];
        for (int i = 0; i < n; i++) {
            int ts, id;
            ts = scanner.nextInt();
            id = scanner.nextInt();
            pair[i] = new Pair(ts, id);

        }

        Arrays.sort(pair, 0, n, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                // TODO Auto-generated method stub
                if (o1.id == o2.id) {
                    return o1.ts - o2.ts;
                }

                return o1.id - o2.id;
            }
        });

        for (int i = 0; i < n; i++) {
            int j = i + 1;
            int cnt = 1;
            int flag = 0;
            int last = pair[i].id;
            while (j < n && pair[j].id == pair[i].id) {
                cnt++;
                if (pair[i].ts + d > pair[j].ts) {

                    if (cnt >= k) {
                        flag = 1;
                        break;
                    }
                } else {
                    while (i < j && pair[i].ts + d < pair[j].ts) {

                        cnt--;
                        i++;
                    }
                    if (i == j)
                        cnt = 1;
                }
                j++;
            }
            if (flag != 0) {
                System.out.println(pair[i].id);
                while (i + 1 < n && pair[i].id == pair[i + 1].id)
                    i++;

            } else {
                i = j - 1;
            }

        }

    }
}

class Pair {
    int ts;
    int id;

    public Pair(int ts, int id) {
        this.ts = ts;
        this.id = id;
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return this.ts + " " + this.id;
    }

}
用户头像
缘_5   2023-03-16 22:23         踩      回复 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N=100010;
    static blog[] q=new blog[N];
    static boolean[] st=new boolean[N];//存储有多少满足是热文
    static int[] cnt=new int[N];//标记点击了多少次
     static class blog implements Comparable<blog>{
        int id,ts;
        public blog(int idd,int tts) {
            id=idd;
            ts=tts;
        }
        public int compareTo(blog o) {//自定义排序
            if(this.ts==o.ts) return this.id-o.id;
            else return this.ts-o.ts;           
        }
        public String tostring() {
            return this.ts+" "+this.id+" \n";
        }
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();//点击次数
        int d=scanner.nextInt();//在一定时间范围
        int k=scanner.nextInt();//不少于多少个赞
        for(int i=0;i<n;i++) {
            int b=scanner.nextInt();
            int a=scanner.nextInt();
            q[i]=new blog(a,b);
        }
        Arrays.sort(q,0,n);
        //双指针,i在j的前面
        for(int i=0,j=0;i<n;i++) {
            int id=q[i].id;
            cnt[id]++;
            while(q[i].ts-q[j].ts>=d) {
                cnt[q[j].id]--;
                j++;
            }
            if(cnt[id]>=k)st[id]=true;
        }
        for(int j=0;j<n;j++) {
            if(st[j])System.out.println(j);
        }

    }

}

###能看我哪里错了吗

用户头像
j简单   2023-03-20 17:25         踩      回复

for(int j=0;j<n;j++) {
if(st[j])System.out.println(j);
}
这里统计的时候不对，是 j <N，要遍历所有的id。

用户头像
zzmm   2023-02-21 21:26         踩      回复

tql orz